非线性序列

非线性序列（non-linear sequence），理学-计算机科学技术-信息安全-密码学-密码编码学-序列密码，由非线性移位寄存器产生的序列。非线性移位寄存器如图所示，与线性移位寄存器类似，唯一的区别在于反馈函数是一个非线性函数。非线性移位寄存器框图级非线性移位寄存器的状态图中一定含有圈，可能还含有枝。当反馈函数可以表示为：时，状态图仅由两两不相交的圈组成。级非线性移位寄存器序列的最大周期为，达到最大周期的序列称作M序列。M序列具有平衡性（任一周期内0和1的个数相等）和随机的游程分布（相同长度的0游程和1游程的个数相等，游程总数为）。整数剩余类环上的线性递归序列蕴含着丰富的非线性结构。20世纪80年代以后，中国国内学者在此领域取得了丰硕的研究成果，特别是证明了保熵定理：环上的本原序列的最高权位序列包含了原序列的全部信息。最高权位序列具有良好的随机性质，特别是复杂的非线性结构。非线性序列越来越多地应用于密码学领域。2004年欧洲启动eSTREAM计划，征集“适合广泛应用的新流密算法”，最终胜出的7个算法中，Grain算法和Trivium算法都是基于非线性移位寄存器的。