论文部分内容阅读
带进位反馈移位寄存器(FCSR)是由美国学者Klapper和Goresky提出的一种新的密钥流发生器.产生的方式决定了FCSR序列天然蕴含了较高的复杂性,它不同于线性移位寄存器序列需要再用其它装置加以改造.由FCSR生成达到最大周期的序列称为l-序列,它有许多类似于m-序列的伪随机性质,如0、1分布均衡,游程分布好等.序列的2-adic复杂度衡量了能产生该序列的最短FCSR的规模.类似于BM算法,存在相应的有理逼近算法可以方便计算序列的2-adic复杂度.FCSR序列,如l-序列,由于2-adic复杂度不高,并不能直接用作密钥流序列,FCSR的线性过滤(F-FCSR)是目前最有效的基于FCSR的序列密码体制.本文继续深入研究了l-序列的其它伪随机性质,这些研究可以为基于FCSR的序列密码设计提供重要参考.设a是以q=pe为连接数,周期T=pe-1(p-1)的l-序列或其采样,再设其指数表示为an=(A·g(mod q))(mod 2),其中g为模q的原根,gcd(A,q)=1.本文第一部分利用剩余类环上的指数和估计研究了l-序列及其采样的自相关性质,结果表明l-序列及其采样具有较好的自相关特性.具体结果如下：1.证明了当位移τ取遍[0,T-1]时,l-序列或其采样序列旦的自相关函数Ca(τ)的均值为0,方差Var,(Ca(τ)=O(q 1n4q).由Chebyshev不等式知,当连接数q适当大时,l-序列及其采样的绝大多数自相关值都是很理想的.2.当连接数为素数p时,证明了l-序列或其采样序列旦的自相关函数Ca(τ)满足：通过计算该三角和,容易给出Ca(τ)的估计值.特别,当位移τ满足gτ(mod p)|=2,(p-1)/2时,序列旦的自相关函数值Ca(τ=O(1n2 p),当p适当大时,该值也较小3.当连接数为素数方幂pe(e≥2)时,证明了对任意正整数i,1≤i≤e/2,当位移τ=kT(2pi)时,l-序列或其采样序列a的自相关函数值为其中1≤k≤2pi-1,gcd(k,p)=1.此结论说明,确实存在某些位移,使得l-序列及其采样的自相关值较大.本文第二部分利用环上本原权位序列的性质研究了l-序列采样的平移不等价性质.具体结果为：4.证明了当连接数为素数方幂时l-序列的采样不平移等价,从而说明在素数方幂情形下,Goresky和Klapper提出多年的猜想(猜想1.1)也是正确的.设丝是环Z/(pe)上由n次本原多项式f(x)生成的本原序列,则称序列：a=u(mod 2)为f(x)导出的n级广义l-序列,简称广义l-序列.它可以看成l-序列的自然推广本文第三部分利用环上本原权位序列的性质进一步研究了广义l-序列的平移不等价性质.设f(x), g(x)为环Z/(pe)上不同的n次本原多项式,得到的具体结果如下：5.当e=1时,在已有结论的基础上,证明了几乎对所有奇素数p,由f(x),g(x)导出的广义l-序列都不平移等价.6.当e≥2时,证明了若f(x)(?) g(x) (mod p),则由f(x), g(x)导出的广义l-序列都不平移等价；而当f(x)(?)g(x)(mod p)时,也几乎对所有本原多项式f(x), g(x),相应的广义l-序列都不平移等价.特别,广义l-序列的任意采样都不平移等价.