线性移位寄存器序列

线性移位寄存器序列（linear shift register sequence），理学-计算机科学技术-信息安全-密码学-密码编码学-序列密码，由线性移位寄存器生成的序列。线性移位寄存器图为二元域上的级线性移位寄存器。为反馈系数，为联结多项式，通常只考虑非退化即的情形。为移位寄存器的初始状态，反馈关系为：称为线性移位寄存器序列。给定一条二元序列，用Berlekamp-Massey算法可以找到生成该序列的最短线性移位寄存器，相应 联结多项式的次数称为此序列的线性复杂度。给定初始状态，级线性移位寄存器生成序列的最大周期为。周期达到最大值的线性移位寄存器序列称为 M序列。此时，联结多项式为本原多项式。周期为的M序列共有条，式中为欧拉函数。M序列具有良好的统计性质，满足由 S.W.戈洛姆(Solomon Wolf Golomb)提出的三个关于周期序列随机性的准则：①一个周期中，0的个数和1的个数基本相等。②一个周期中，相同长度的0-游程和1-游程的数目基本相等。③自相关函数是二值函数。M序列有很多应用。