非线性反馈移位寄存器

非线性反馈移位寄存器（NLFSR, Nonlinear feedback shift register）是一種移位寄存器，和線性反饋移位暫存器（LFSR）相對。NLFSR的大体电路逻辑和LFSR相似，但是其反馈逻辑是由异或门 (xor) 和与 (and) 门构成的，而LFSR中仅存在异或门 (xor)。

从代数表达式来看，异或门是加法 (+)，而与门是乘法 (*)。由加法构成的反馈逻辑，其反馈表达式的最高项次数不会增长，而由乘法参与的反馈表达式项次数会增长、并可能超过定义多项式的最高项。NLFSR 的设计巧妙地结合了异或门和与门，这种结构使其在生成伪随机序列方面表现出非线性的特性。异或门的使用确保了反馈逻辑中不引入高次数的项，从而保持了较低阶的表达式形式。而与门的引入则使得反馈逻辑的非线性度增强，这对于提高 NLFSR 的复杂性和抵抗密码分析攻击具有重要意义。

Janusz Szmidt在"The Search and Construction of Nonlinear Feedback Shift Registers"這篇文章中給出了較為詳盡的討論，具體請參見 https://web.archive.org/web/20140529084401/http://www.math.uni-magdeburg.de/~fq11/talks/Szmidt.pdf

參考文獻

• Generation of Nonlinear Feedback Shift Registers with special-purpose hardware （页面存档备份，存于互联网档案馆）
• The Synthesis of Nonlinear Feedback Shift Registers （页面存档备份，存于互联网档案馆）
• On Analysis and Synthesis of(n,k)-Non-Linear Feedback Shift Registers （页面存档备份，存于互联网档案馆）