线性反馈移位寄存器（LSFR）

线性反馈移位寄存器（LSFR）

流密码的流密钥产生器可以通过线性驱动和非线性组合两部分来实现。而线性驱动部分可以由线性反馈移位寄存器（LFSR）来实现。
线性反馈移位寄存器(LFSR)：通常由移位寄存器和异或门逻辑组成。其主要应用在：伪随机数，伪噪声序列，计数器，BIST，数据的加密和CRC校验等。

其中，gn为反馈系数，取值只能为0或1，取为0时表明不存在该反馈之路，取为1时表明存在该反馈之路；这里的反馈系数决定了产生随机数的算法的不同。用反馈函数表示成y=a0x^ 0+a1x+a2x^2…反馈函数为线性的叫线性移位反馈序列，否则叫非线性反馈移位序列。

LFSR的初始值被称为伪随机序列的种子，影响下一个状态的比特位叫做抽头。理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项式加1就是其反馈多项式，必须是一个本原多项式，也就是说这个多项式不可约，比方下图的抽头序列为，其对应的反馈多项式为，其对应的线性反馈移位寄存器电路如下所示。