De Bruijn序列构造的新方法

New Constructions of De Bruijn Sequences

采用非线性反馈移位寄存器作为驱动部件是序列密码算法的新趋势,序列的密码性质研究成为密码学的一个重要课题。DeBruijn序列是一类特殊的序列,具有周期大和线性复杂度高等良好的伪随机性质。如何构造DeBruijn序列一直是序列研究的一个公开问题。通过考察两类特征函数的圈结构及圈上共轭状态的分布规律,给出两种构造deBruijn序列特征函数的方法。

It is a new trend to use a nonlinear feedback shift register as the driving building block in stream cipher algorithms.Therefore,the study of cryptographic properties of sequences becomes an important topic in cryptography.De Bruijn sequences are one special class of sequences and have good pseudo-random properties such as large period and high linear complexity.Constructing de Bruijn sequences has been an open problem in the study of sequences.By discussing the cycle structure of two classes of characteristic functions and the distribution of conjugate pairs on these cycles,this paper gives two methods for constructing the characteristic functions of de Bruijn sequences.