LFSR伪随机数生成器

• LFSR英文名为Linear feedback shift register，中文翻译过来就是线性反馈移位寄存器，其伪随机数生成的特点已经包含在LFSR的名称中，也就是线性、反馈这两个词。
• 由于LFSR是非常容易使用硬件实现的，所以在以前很多流密码的密钥都是通过LFSR伪随机数生成算法来实现的，但是该伪随机数生成的算法在密码学体制中是比较不安全的，容易被预测到。
• 本篇文章写于2025.6.16但是写的不怎么好，而在2025.9.11在图书馆随便看看，看到了这本书，从数学原理讲LSFR，于是决定重写博客，重新学习LSFR相关的。

LFSR

• LFSR是指给定前一状态的输出，将该输出的线性函数在用作输入的移位寄存器。其中异或运算是最常见的单比特线性函数，对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。也就是先进行异或运算再进行位移运算
• LFSR是计算机可以比较快的构造出一个拟完美序列。

LFSR的两种形式

• LFSR其实不止上面介绍的一种形式，其实还有另一种形式。
• 对于上面介绍的这种，是比较经典的，将其称为Fibonacci型，其实就是指定抽头影响输入位。

• 还有一种LFSR类型，该类型为Galois型，这种类型是输出位送给输入位后逐位异或，从而影响其他位，得到伪随机。

• 大致介绍一下LFSR的工作流程：
  • 首先FF0、FF1、FF2、...、FFn会被初始化bit位。
  • 接着CLK时钟，发出一个脉冲，这就会使得
    • $FF_n$的值输出出去（其中输出其实还要画一个箭头，这边只有参与异或的箭头），$FF_n$的值会输出到两个地方，其中一个地方是输出给用户使用，另一个输出是参与生成下一个FF0的运算。
    • 接着$FF_{n-1}$的值就会被输出（移动）到$FF_{n}$这个寄存器中，$FF_{n-2}$的值就会被输出（移动）到$FF_{n-1}$这个寄存器中，以此类推，这就是移位
  • 输出的过程中，其实还会将输出的值输出给$g_1、g_2、...、g_{n}$就会参与运算，运算的结果就是$FF_0$的值，这就是反馈。
• 上面就是LFSR的大致过程，接下来展示一个真实的LFSR电路图，由于LFSR的特性，其是比较容易在硬件中实现的，逻辑电路图并不复杂。其组成其实就是n个触发器，加上一些异或门再通过导线连接即可得到一个硬件的LFSR。

LFSR算法描述

• 我们先来给出一张图片，这张图片就简单介绍了LFSR算法。这张图主要做了一下几个事情：

  • 对于初始的状态$a_na_{n-1}...a_{2}a_{1}$，经过一个线性函数$f(a_1,a_2,...,a_n)$的运算，其实$f(a_1,a_2,...,a_n)$这个线性函数就是异或操作，即$f(a_1,a_2,...,a_n)=a_1\oplus a_2 \oplus ...\oplus a_n$,得到一个结果作为我们后续的输入的bit值，所以这个函数运算结果只有0或者1，先暂时保存这个值

  • 之后将$a_na_{n-1}...a_2a_1$经过位移后整体就变成$a_{n-1}a_{n-2}...a_1a_0$，此时$a_0$其实就是作为输出值了

  • 最后我们再将$f(a_1,a_2,...,a_n)$运算得到的结果传递给$a_n$，此时就构成了新的一组$a_na_{n-1}...a_2a_1$序列

  • 之后像这样不断的线性位移计算，我们就能得到这些二进制序列，我们每线性位移n次取一次序列，这样就得到了n位伪随机数

  • 注意：不一定所有的位都参与线性运算，一般只选择几个位参与线性运算

有几个注意点：

1. 将参与线性运算$f(a_1,a_2,...,a_n)$的位称为抽头，也就是LFSR状态下影响输入的位
2. LFSR最右边的位为输出位，同时它始终也是抽头。
3. 抽头是有顺序的异或，然后反馈到最左边的位。
4. 最右边的位序列称为输出流，如上图所示其实我们的输出流其实是$a_1$先输出出来,然后$a_2$，最后才是$a_n$
5. 最大长度LFSR产生m序列具有$2^m-1$种状态，寄存器全零状态的时候线性位移后还是全零（关于m序列的概念这里不多说）

• 接下来我们使用Python实现一下简单的32位LFSR伪随机数：

def _int32(x):
    return x & 0xFFFFFFFF

class LFSR:
    def __init__(self,seed):
        # seed作为初始化寄存器的一个种子
        # 规定二进制序列是这样的an an-1 ... a2 a1与上图描述一致
        self.seed = _int32(seed)

    def xor(self):
        # 规定a26 a16 a11 a1都作为抽头
        x = bin(self.seed)[2:].zfill(32)
        tap = [25,15,10,0]
        tmp = 0
        for i in tap:
            tmp ^=int(x[i],2)
        return tmp

    def lshift(self,an,reg):
        # 进行位移运算
        return _int32((an<<31)|(reg>>1))

    def LSF(self):
        # 生成32位的随机数
        # 其实也可以直接LSF一次,而不用32次
        for i in range(32):
            an = self.xor()
            self.seed=self.lshift(an,self.seed)
        return self.seed

LFSR = LFSR(0xF75a15663499)
for i in range(10):
    print(LFSR.LSF())

LFSR数学表示

LFSR例子

• 先举一个例子看看：$Z_2$上周期为7的拟完美序列如下：

  • $\alpha=1001011...=a_0a_1a_2a_3a_4a_5a_6....$，观察$a_0、....、a_7$这七个数之间的关系。
  • 注意到有如下关系，发现前三位$a_0、a_1、a_2$确定下来了，这个序列的关系就可以确定了：

  $$a_3=a_1+a_0\\a_4=a_2+a_1\\a_5=a_3+a_2\\a_6=a_4+a_3\\a_7=a_0=a_5+a_4$$

  • 这样我们可以通过递推公式写出来关系式：$a_{k+3}=a_{k+1}+a_{k},(k=0,1,2...)$，这是一个三阶递推公式。

LFSR数学推导

• 从上面的LFSR例子可以看到，我们用递推关系很好表示出来这个序列，所以一开始我们就使用递推公式来描述LFSR。
• 对于LFSR来说，需要有周期，并且周期长，这样才是好的LFSR，所以接下来需要研究它的周期。在研究周期之前，除了递推这个数学描述之外，LFSR还可以用矩阵描述、特征多项式描述，接下来通过递推公式逐渐引入这两个描述。
• 考虑一个$Z_2$上的n阶线性常系数齐次递推关系式，可以用LFSR实现这个递推序列，接下来要研究它是否有周期，周期是否很大：
  • $a_{k+n}=c_1a_{k+n-1}+c_2a_{k+n-2}+...+c_{n-1}a_{k+1}+c_na_{k},(k=0,1,2,...,c_n≠0)$该式子记为①
  • 设正整数$d$是序列$\alpha=a_0a_1a_2...$的一个周期，定义式子为：$a_{i+d}=a_{i}$该式子记为②，满足②式的最小正整数$l$称为$\alpha$的最小正周期。
  • 等价条件：$u$是$\alpha$的周期$\Leftrightarrow u$是最小正周期$l$的正整数倍
• 目前来说只有一个递推式子研究周期还是比较困难的，所以我们引入如下方程组：

$$\begin{cases} \begin{array}{l} a_{k+n}&=c_1a_{k+n-1}+&c_2a_{k+n-2}+&...+&c_{n-1}a_{k+1}+&c_na_{k}\\ a_{k+n-1}&=a_{k+n-1}\\ a_{k+n-2}&=&a_{k+n-2}\\ \vdots\\ a_{k+1}&=&&&a_{k+1} \end{array} \end{cases}$$

• 这样一来就可以写成向量矩阵的形式，描述如下，从而记$A = \begin{bmatrix} c_1&c_2&\dots&c_{n-1}&c_n\\ 1&0&\dots&0&0\\ 0&1&\dots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\dots&1&0 \end{bmatrix}$称为递推关系①式的生成矩阵：

$$\begin{pmatrix} a_{k+n} \\ a_{k+n-1}\\ a_{k+n-2}\\ \vdots \\ a_{k+1} \end{pmatrix}=\begin{bmatrix} c_1&c_2&\dots&c_{n-1}&c_n\\ 1&0&\dots&0&0\\ 0&1&\dots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\dots&1&0 \end{bmatrix} \begin{pmatrix} a_{k+n-1} \\ a_{k+n-2}\\ a_{k+n-3}\\ \vdots \\ a_{k} \end{pmatrix}$$

• 接下来对于初始值$a_0,a_1,...,a_{n-1}$如果确定了，我们希望各个位数求出来，

  • 对于上述式子，我们令$k=0$那么我们就有：

  $$\begin{pmatrix} a_{n} \\ a_{n-1}\\ a_{n-2}\\ \vdots \\ a_{1} \end{pmatrix}=\mathbf{A} \begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}$$

  • 令$k=1$就有：

  $$\begin{pmatrix} a_{n+1} \\ a_{n}\\ a_{n-1}\\ \vdots \\ a_{2} \end{pmatrix}=\mathbf{A} \begin{pmatrix} a_{n} \\ a_{n-1}\\ a_{n-2}\\ \vdots \\ a_{1} \end{pmatrix}=\mathbf{A}^{2}\begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}$$

  • 以此类推就有，这样不就有了个类似于通项公式的东西了么，我们将下面的式子记为④式

  $$\begin{pmatrix} a_{k+n-1} \\ a_{k+n-2}\\ a_{k+n-3}\\ \vdots \\ a_{k} \end{pmatrix}=\mathbf{A}^{k} \begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}$$

命题1：

$d$是由$n$阶递推关系①式产生的$Z_2$上序列$\alpha=a_0a_1a_2...a_{n-1}...$的一个周期的充分必要条件是$\mathbf{A}^{d}\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix} = \begin{pmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}$

推论1：

若$A^{d}-I=0$，则$d$是①式产生的任意序列的周期

• 证明：

  • 由$d$是序列的周期就可以得到：$a_{i+d}=a_i,i=0,1,2...$
  • 利用递推关系①式$\Rightarrow$$\begin{pmatrix}a_{d+n-1} \\ a_{d+n-2} \\ a_{d+n-3} \\ \vdots \\ a_{d} \end{pmatrix}=\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}$，这个式子再由④式得到：$\mathbf{A}^{d}\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0}\end{pmatrix}=\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}$
  • 这就得到了$\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}$是$A^{d}$的属于特征值1的一个特征向量。
  • 从而就有$(A^{d}-I)\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}=0$

• 回过来看式子①：

  • 通过一系列的递推我们就可以得到如下的方程组：

  $$\begin{cases} \begin{array}{l} a_{n+n-1}&=c_1a_{n+n-2}+...+c_{n-1}a_{n}+c_na_{n-1}\\ \vdots\\ a_{n+1}&=c_1a_n+...+c_{n-1}a_2+c_{n}a_1\\ a_{n}&=c_1a_{n-1}+...+c_{n-1}a_1+c_na_0 \end{array} \end{cases}$$

  • 写成向量的的形式，这一看这个结构不就是线性表出

  $$\begin{pmatrix} a_{n+n-1} \\ a_{n+n-2} \\ a_{n+n-3} \\ \vdots \\ a_{n} \end{pmatrix}= c_1\begin{pmatrix}a_{n+n-2} \\ a_{n+n-3} \\ a_{n+n-3} \\ \vdots \\ a_{n-1} \end{pmatrix} +...+c_{n-1}\begin{pmatrix}a_{n} \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{1} \end{pmatrix} +c_n\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}$$

  • 再使用④式$\begin{pmatrix} a_{k+n-1} \\ a_{k+n-2}\\ a_{k+n-3}\\ \vdots \\ a_{k} \end{pmatrix}=\mathbf{A}^{k} \begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}$带入到上面的向量形式的方程就有如下，对于一切$a_0,a_1,...,a_{n-1}\in Z_2$都成立，记下面的式子为⑤式

  $$(A^{n}-c_1A^{n-1}-...-c_{n-1}A^{1}+c_nI)\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}=\begin{pmatrix}0 \\0\\0\\\vdots \\0 \end{pmatrix}$$

  • 由一个矩阵乘上任意一向量都是零矩阵，那么这个矩阵一定是零矩阵，可以得到，记该式子为⑥式：

  $$A^{n}-c_1A^{n-1}-...-c_{n-1}A^{1}+c_nI=0$$

  • 令$f(x)=x^{n}-c_1x^{n-1}-...-c_{n-1}x-c_n\in Z_2[x]$，此时$f(A)=0$，只要递推关系式①给了，我们就能确定这个多项式。而多项式和递推关系可以互推，这样的多项式我们就称为递推关系式①的特征多项式。从而有命题⑥

命题2

设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵则$f(A)=A^{n}-c_1A^{n-1}-...-C_{n-1}A-c_nI=0$

定理1

设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，若$f(x)|x^{d}-1$，则$d$是$n$阶递推关系①产生的任意序列的周期。

• 证明：
  • 存在$h(x)\in Z_2[x]$使得$x^{d}-1=h(x)f(x)$，用生成矩阵$A$带入$x$得到
  • 可以得到：$A^{d}-I=h(A)f(A)=0$
  • 由推论1可以得到$d$是$n$阶递推关系①产生的任意序列的周期。

定理2

设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，设$f(x)$在$Z_2$上不可约，若$d$是$n$阶递推关系①产生的一个非零序列$\alpha = a_0a_1...a_{n-1}a_n...$的一个周期，则$f(x)|x^{d}-1$

• 证明：使用反证法证明
  • 假设$f(x)\not|x^d-1$，则$(f(x),x^{d}-1)=1$
  • 从而存在$u(x),v(x)\in Z_2[x]$，使得$u(x)f(x)+v(x)(x^{d}-1)=1$，这个式子就是裴蜀定理在多项式中的推广
  • $x$用生成矩阵$A$带入，就有$u(A)f(A)+v(A)(A^{d}-I)=I$
  • 由命题2可以得到$v(A)(A^{d}-I)=I$，$v(A)(A^{d}-I)\begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}=\begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}$
  • 从而得到$\begin{pmatrix}0 \\ 0 \\ 0 \\ \vdots \\0\end{pmatrix}=\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}$，与$\alpha$是非零序列矛盾。
• 我们还希望这个$n$阶递公式的生成的任意序列都有周期，接下来我们就要从特征多项式入手：
  • 由⑥式$A^{n}-c_1A^{n-1}-...-c_{n-1}A-c_nI=0$可以得到：$A^{n}=c_1A^{n-1}+...+c_{n-1}A+c_nI$记为式子⑦
  • 从而：$A^{n+1}=c_1A^{n}+c_2A^{n-1}+...+c_{n-1}A^2+C_nA=c_1(c_1A^{n-1}+...+c_{n-1}A+c_nI)+...+c_nA$
  • 说明$A$的任意非负整数次幂都可以属于下面这个集合：$\Omega=\{b_1A^{n-1}+b_2A^{n-2}+...+b_{n-1}A+b_nI|b_i \in Z_2,i=1,2,....\}$
  • 而$\Omega$这个集合中元素个数有$2^{n}$个，但是有些$A$的次幂可以由多个多项式生成相同的结果，所以$|\Omega|≤2^n$
  • 从而$\Omega$中的非零矩阵至多有$2^{n}-1$个，下述$2^{n}$个矩阵，$I,A,A^{2},...,A^{2^{n}-1}$，由于生成矩阵$|A|=c_n≠0$，因此$A$可逆矩阵。
  • 从而上述$2^n$个矩阵都是非零矩阵，于是存在一对$i,j$满足：$A^{i}=A^{j},0≤i<j≤2^{n}-1$，从而就有$I=A^{j-i}$，即$A^{j-i}-I=0$
  • 由推论1可以得到，$j-i$是$n$阶递推关系①产生的任意序列的周期
  • 从而任何一个①产生的任意序列的最小正周期$l≤j-i≤2^{n}-1$，于是得到定理3

定理3

$n$阶递推关系①产生的任一序列都有周期，并且最小正周期不超过$2^{n}-1$

• 我们希望周期越大越好，所以引入了如下的定义

定义1

设$\alpha$是$Z_2$上$n$阶常系数线性齐次递推关系产生的序列，如果$\alpha$的最小正周期达到$2^{n}-1$，那么称$\alpha$是$Z_2$上的一个m序列。

• 最后我们还要分析，这个线性递推关系满足的什么条件才会是m序列，于是推导出了定理4，接下来先分析一下：
  • 由定理1可以得到若$f(x)|x^{2^n-1}-T$则$2^{n-1}$是$\alpha$的一个周期。
  • $\alpha$的最小正周期$l|2^{n}-1$
  • 那么我们希望：对于$d|2^{n}-1$，且$0<d<2^{n}-1$，$d$不是$\alpha$的周期。若$f(x)$在$Z_2$上不可约，且$f(x)\not|x^{d}-1$则根据定理2得到，$d$不是$\alpha$的周期。

定理4

设$f(x)$是$n$阶递推关系①的特征多项式，如果满足：

1. $f(x)$在$Z_2$上不可约
2. $f(x)|x^{2^{n}-1}-T$
3. 对于$d|2^{n}-1$，且$0＜d＜2^{n-1}$，都有$f(x)\not|x^{d}-1$

那么①产生的任一非零序列$\alpha$是m序列

定义2

$Z_2$上的一个$n$次多项式$f(x)$如果满足定理4中的三个条件，那么称$f(x)$是$Z_2$上的一个本原多项式（这个本原多项式与有理数上的本原多项式是不同的概念）

注：从定义2出发，我们可以重新这样叙述定理4，如果$n$阶递推关系①的多项式是$Z_2$上的本原多项式，那么①产生的任何序列都是m序列。

定理5

$Z_2$上的m序列都是拟完美序列。

总结

命题1：

$d$是由$n$阶递推关系①式产生的$Z_2$上序列$\alpha=a_0a_1a_2...a_{n-1}...$的一个周期的充分必要条件是$\mathbf{A}^{d}\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0}\end{pmatrix}=\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}$

推论1：

若$A^{d}-I=0$，则$d$是①式产生的任意序列的周期

命题2

设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵则$f(A)=A^{n}-c_1A^{n-1}-...-C_{n-1}A-c_nI=0$

定理1

设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，若$f(x)|x^{d}-1$，则$d$是$n$阶递推关系①产生的任意序列的周期。

定理2

设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，设$f(x)$在$Z_2$上不可约，若$d$是$n$阶递推关系①产生的一个非零序列$\alpha = a_0a_1...a_{n-1}a_n...$的一个周期，则$f(x)|x^{d}-1$

定理3

$n$阶递推关系①产生的任一序列都有周期，并且最小正周期不超过$2^{n}-1$

定义1

设$\alpha$是$Z_2$上$n$阶常系数线性齐次递推关系产生的序列，如果$\alpha$的最小正周期达到$2^{n}-1$，那么称$\alpha$是$Z_2$上的一个m序列。

定理4

设$f(x)$是$n$阶递推关系①的特征多项式，如果满足：

1. $f(x)$在$Z_2$上不可约
2. $f(x)|x^{2^{n}-1}-T$
3. 对于$d|2^{n}-1$，且$0＜d＜2^{n-1}$，都有$f(x)\not|x^{d}-1$

那么①产生的任一非零序列$\alpha$是m序列

定义2

$Z_2$上的一个$n$次多项式$f(x)$如果满足定理4中的三个条件，那么称$f(x)$是$Z_2$上的一个本原多项式（这个本原多项式与有理数上的本原多项式是不同的概念）

注：从定义2出发，我们可以重新这样叙述定理4，如果$n$阶递推关系①的多项式是$Z_2$上的本原多项式，那么①产生的任何序列都是m序列。

定理5

$Z_2$上的m序列都是拟完美序列。

LFSR破解

• 对于LFSR的破解需要用上一个经典的算法也就是 Berlekamp-Massey算法。这里建议先去学习一下Berlekamp-Massey算法，先从它的数学抽象出来的问题入手，在破解LFSR的时候会更有助于理解。Berlekamp–Massey 算法 - OI Wiki
• 对于Berlekamp-Massey算法，就不在这里详细介绍，这里只介绍Berlekamp-Massey算法在破解LFSR中的应用。

LFSR深入理解

• 接下来要介绍一些相关的定义和定理作为学习Berlekamp-Massey算法的前置知识。

知识点1

假设一个LFSR长度为L，LFSR的最初状态其实就等于LFSR所产生的序列的前L位输出。如下图所示，序列$a_0、a_1、...、a_n$其实就是长度为N的LFSR的初始状态。

从第$L+1$位开始的所有输出，完全由LFSR的反馈结构和初始状态决定，说明了一旦LFSR的反馈结构确定并且设置了初始状态，那么输出序列就唯一确定

知识点2

当我们要用阶(其实是LFFR的长度)为L的LFSR，来生成长度为$N$的序列其实会出现以下两种情况：

1. 当L>=N时，该LFSR一定能生成长度为$N$的序列，但是并不是最短的一个LFSR
2. 当L<N时，如果该LFSR能生成长度为$$N$$的序列，那么从第$L+1$位开始就必须满足递推式$s_n=\sum^{L}_{i=1}c_{i}s_{n-i}~mod~2$

定理1:

如果某个长度为L的LFSR能生成长度为N的序列，$s_0、s_1、...、s_{N-1}$,但是无法生成第$s_{N}$项，那么任何一个可以完整生成序列$s_0、s_1、...、s_{n}$的LFSR，其长度必须满足$L^{'}≥N+1-L$，这个其实是B-M算法的下界定理

引理:

如果一个长度为n的LFSR记为$L_{n}(s)$，生成了$s_0,s_1,...,s_{N-1}$但是该LFSR并不能生成$s_0,s_1,...,s_{n-1},s_{n}$，那么就有$L_{n+1}(s)≥max[L_{N}(s),N+1-L_{N}(s)]$

定理2:

如果一个长度位N的LFSR