用密码学的知识解决:已知某线性反馈移位寄存器的反馈函数对应的特征多项式是p(x)=x4+x+1，求： （1）该线性反馈移位寄存器的线性递推式和结构图； （2）设初始状态是(a1,a2,a3,a4)=（1，0，0，0），求此线性反馈移位寄存器产生的序列及其周期。

首先我们来解释一下题目中的术语：

- 线性反馈移位寄存器（LFSR）是一种在密码学中广泛使用的序列生成器，它由若干个寄存器组成，每个寄存器只能存储0或1。在每个时刻，LFSR 会根据寄存器中的值计算出一个新的位，然后将这个新位插入到寄存器的最高位，同时将寄存器中的位向右移动一位。这个新位就是 LFSR 的输出，而输入则是一个外部控制信号（称为“反馈”信号），它会对新位的计算产生影响。
- 反馈函数是一个布尔函数，它描述了反馈信号如何从寄存器中的位计算出来。在本题中，反馈函数对应的特征多项式是 p(x) = x^4 + x + 1，这意味着反馈函数是一个 4 位的线性函数，计算方式为对于任意 4 位寄存器的值 a1, a2, a3, a4，反馈函数的输出为 a1 xor a4 xor 1。

现在我们来回答题目的两个问题：

（1）该线性反馈移位寄存器的线性递推式和结构图

根据 LFSR 的定义，我们可以列出它的线性递推式：

an = an-4 xor an-1

其中 a1, a2, a3, a4 分别表示 4 个寄存器的值，an 表示在第 n 个时刻 LFSR 的输出。由于本题中寄存器的个数为 4，所以这个式子就是该 LFSR 的递推式。

至于结构图，我们可以将 4 个寄存器和反馈函数按照下图连接起来：

     +-------+
     |       |
     v       |
+----+---+   |
|        |<--+
|  p(x)  |
|        |---+
+----+---+   |
     |       |
     v       |
     +-------+

其中箭头表示数据流的方向，反馈函数 p(x) 计算 a1 xor a4 xor 1 的结果并作为输入送回寄存器。这样就形成了一个简单的 LFSR。

（2）设初始状态是 (a1, a2, a3, a4) = (1, 0, 0, 0)，求此线性反馈移位寄存器产生的序列及其周期

根据递推式，我们可以递归地计算出 LFSR 的输出序列：

a1 = 1
a2 = 0
a3 = 0
a4 = 0
a5 = a1 xor a4 = 1
a6 = a2 xor a5 = 1
a7 = a3 xor a6 = 1
a8 = a4 xor a7 = 0
a9 = a5 xor a8 = 1
a10 = a6 xor a9 = 0
a11 = a7 xor a10 = 1
a12 = a8 xor a11 = 1
a13 = a9 xor a12 = 0
a14 = a10 xor a13 = 1
a15 = a11 xor a14 = 0
a16 = a12 xor a15 = 1
a17 = a13 xor a16 = 1
a18 = a14 xor a17 = 0
a19 = a15 xor a18 = 1
a20 = a16 xor a19 = 0
...

可以看出，LFSR 的输出序列是一个无限长的伪随机序列，其中每个位都是 0 或 1。为了方便起见，我们可以将序列分成若干个周期，每个周期包含 15 个位：

1 1 1 0 1 0 1 1 0 1 0 1 0 1 1

可以验证，这个周期满足递推式，即对于任意正整数 n，有：

an = a(n+15)

因此，这个周期的长度为 15。