论文部分内容阅读
伪随机序列在密码学、通信和计算机等领域有着十分重要的作用.如何评价伪随机序列是序列密码中的重要问题.S.W.Golomb认为“好”的伪随机序列在周期长、易生成的基础上需满足:元素分布均衡、好的游程分布、理想的自相关特性.随着伪随机序列研究的不断深入,对于密码意义下“好”的伪随机序列提出了新的要求.1969年,Massey提出了Berlekamp-Massey综合算法后,线性复杂度便成为评价序列伪随机性的重要指标.然而,线性复杂度高的序列其安全强度未必高.例如序列(110010111001011100100)∞的线性复杂度和周期都达到最大值21,但这是一条极不安全的序列.若改变该序列每周期中的一个比特,则序列线性复杂度降为3.因此,人们提出了另一个衡量序列伪随机性的重要指标:k-错线性复杂度.本文主要研究了周期序列k-错线性复杂度分布,包括k-错线性复杂度值、给定k-错线性复杂度的序列计数、k-错线性复杂度均值以及线性复杂度下降点等问题.主要结果如下:1.对于2n-周期二元序列,当其线性复杂度为2n-1时,计算了该序列2-错(或3-错)线性复杂度的所有可能值以及具有给定2-错(或3-错)线性复杂度序列的条数,由此计算了该序列2-错(或3-错)线性复杂度的均值,即给出了序列2-错(或3-错)线性复杂度的分布情况.2.讨论了任一2n-周期二元序列2-错线性复杂度的分布,具体计算了该序列2-错线性复杂度的所有可能值以及具有给定2-错线性复杂度序列的条数,进一步给出了2n-周期二元序列2-错线性复杂度的均值.3.简单讨论了2n-周期二元平衡序列的2-错线性复杂度的分布.4.给出了Fp上pn-周期序列所有可能的1-错线性复杂度值以及具有给定1-错线性复杂度的序列条数.从而得到了Fp上pn-周期序列1-错线性复杂度均值,更进一步,计算了Fp上pn-周期随机序列k-错线性复杂度均值的界.5.给出了周期为2pn二元序列线性复杂度的第一下降点的上界,并指出了周期为2p的二元序列在大多数情况下达了到该上界.6.给出了Fq上周期为2pn序列线性复杂度第一下降点的上界.7.对分圆多项式Φpq(x)及其因子进行了分析,并给出了周期为pqn二元序列线性复杂度的第一下降点的上界.