一种伪随机序列的线性复杂度及其稳定性研究

Study on the linear complexity and stability of a Pseudorandom Sequence

信息安全领域中,传统使用m序列为基序列,对序列进行非线性组合、非线性滤波和非均匀采样等产生线性复杂度很高的序列,其线性复杂度的稳定性却不如意。提出伪随机序列称为m子序列,m子序列通过改变m序列的状态转换次序而得到的序列,m子序列改变了m序列的输出次序,是非线性序列。实验数据表明其线性复杂度是移位寄存器个数的指数倍,同时其线性复杂度的稳定性很高,此序列的k-error线性复杂度随着移位寄存器的个数的增加而不变。

In the information security area, traditionally m-sequence is used as the base sequence on which non-linear combination, non-linear filtering and non-uniform sampling are applied to generate a sequence with high linear complexity. Yet the stability of linear complexity of such a sequence is not satisfactory. In this paper, we propose m-subsequence which is generated by changing the state transition order of the m-sequence. Since the m-subsequence is made by changed the order of the m -sequence, it is a non-linear sequence. The linear complexity is shown to be stable and exponential in the length of the shift register by testing data. In addition, the k-error linear complexity remains the same as the length of the shift register grows.