线性反馈移位寄存器（Linear Feedback Shift Register，简称LFSR）是一种电子数字电路，通常用于随机数生成、序列产生、加密算法和错误检测等领域。它由若干个锁存器组成，每个锁存器有一个输出端和一个输入端，输入端与总线相连，输出端连到反馈回路中。
在LFSR中，锁存器中的数据按照一定规律进行移位，移位后的数据通过异或运算与反馈回路中的某些数据结合，从而产生新的数据，以循环的方式形成一个数据序列。这个序列的周期长度是有限的，且等于LFSR中锁存器数量的2次方减1。
LFSR的实现可以采用硬件电路或软件算法。硬件实现时，每个锁存器可由一个D触发器和一个异或门组成，每个异或门的输入由若干个锁存器的输出通过选择器选择产生。软件实现时，可使用多项式来描述反馈回路，即将所有异或门的输出按位异或得到一个多项式，称为反馈多项式，用二进制数表示，将其写成一个m位的二进制数，记作F(x)=f(m-1)x^{m-1}+...+f(1)x+f(0)，其中f(0)到f(m-1)为0或1。以该多项式为反馈回路，构建一个m位的移位寄存器即可。
LFSR可用于密码学中的伪随机数生成算法。由于其周期长度很长，且具有良好的统计特性，因此在保证安全性的前提下，可用于加密算法和认证协议。
0