论文部分内容阅读
反馈移位寄存器是一种重要的电子器件,其生成的二元序列在通信、密码等领域得到广泛应用。例如,在连续波雷达中用作测距信号,在多址通信中用作地址信号,在数字通信中用作群同步信号,此外还可用作噪声源以及在保密通信中起到加密作用等。序列密码作为三大密码体制之一,在密码学中有着重要的地位。反馈移位寄存器是序列密码的核心部件。早期序列密码主要基于线性反馈移位寄存器设计,并对由线性反馈移位寄存器产生的序列进行非线性改造从而生成密码流,例如过滤生成器、组合生成器等。由于相关攻击和代数攻击的影响,基于此类模型已经很难设计出安全高效的序列密码算法。进入21世纪,采用非线性反馈移位寄存器替代线性反馈移位寄存器生成驱动序列已经成为现代序列密码设计的主流趋势。非线性反馈移位寄存器成为当前序列密码领域理论研究的热点课题之一。与此同时,非线性反馈移位寄存器由于缺乏有效的代数工具刻画,研究成果依旧十分匮乏,许多基础问题也没有得到解决,例如周期、圈结构等,因此也是序列密码领域研究的难点之一。 本报告中主要研究了两类线性反馈移位寄存的圈结构和共轭对分布,并利用并圈方法构造了大量新的de Bruijn序列。主要成果包括: (1)研究了一类以p2(x)为特征多项式的线性反馈移位寄存器,其中p(x)∈F2[x]是一个n次本原多项式,n≥2。给出了它的圈结构和共轭对分布,彻底解决了圈之间的共轭对的计数问题,得到了邻接图。利用并圈方法,得到了一类新的de Bruijn序列和相应的极大周期非线性反馈移位寄存器。 (2)研究了以f2(x)为特征多项式的线性反馈移位寄存器,其中f(x)∈F2[x]是一个n次不可约多项式,n≥2。给出了它的圈结构、共轭对计数以及共轭对分布求解方法。 (3)进一步研究了以pm(x)为特征多项式的线性反馈移位寄存器,其中p(x)为F2上的n次本原多项式,n≥2,m=2d,d≥1。提出了该类寄存器序列的分解表示、L-表示以及特征的概念,在此基础上给出了它的圈结构、共轭对计数以及求解共轭对分布的算法。