随机周期序列线性复杂度的方差

随机周期序列线性复杂度的方差

0随机周期序列线性复杂度的稳定性设置s=s0、s1、s2。。。设置有限区域fq的循环序列。序列s被称为n周期。当ss为时，所有i0的序列s可以表示为s=（s0、s1、sn-1），然后设置sn（x）。N周期序列的线性复杂度L(S)则是最小的非负整数c,使得存在系数d1,d2,…,dc∈Fq,有如下等式即L(S)为首一多项式m(x)=xc+d1xc-1+…+dc-1x+dc∈Fq[x]的次数,多项式m(x)称为序列S的极小多项式.L(S)=0当且仅当S是全0序列,L(S)为能生成S的最小线性反馈移位寄存器的长度.为了研究周期序列的线性复杂度,Günther和Blahut首先采用广义离散傅立叶变换作为主要工具,研究周期序列的线性复杂度性质.此后,Meidl和Niederreiter利用这一方法得到了随机周期序列线性复杂度的期望值.可是衡量周期序列的稳定性仅仅用随机周期序列线性复杂度的期望值是不够的,于是我们可以用随机周期序列线性复杂度的方差进行衡量.本文采用广义离散傅叶变换,通过计算得到了随机周期序列线性复杂度的方差,这个结果与文献中的结果有着不同的表达形式,可以证明这两个结果实质上是等价的.然后利用本文的结果确定了某些重要周期的随机周期序列线性复杂度的方差,并且分析了随机周期序列线性复杂度的方差的渐近性质.下面第一节里,介绍广义傅立叶变换的性质,周期序列的线性复杂度与分圆陪集的势的关系.第二节里面,将计算出周期为N的序列的线性复杂度的方差,并且利用计算的结果对不同类别的周期序列进行了随机周期序列线性复杂度的方差的渐近性质的分析.1广义离散傅立叶变换矩阵的结构性质本节主要介绍Meidl和Niederreiter在文献中得到的一些重要结果.定义1设g(x)=∑iaixi是定义在多项式环F[x]的多项式,系数在域F上,对于多项式g(x),t≥0,t阶的Hasse导数定义如下:由此可见,g(t)(x)=t!g[t](x),其中g(t)(x)是多项式g(x)的t阶导数.定义2N元广义离散傅立叶变换如下:设SN=(S0,s1,s2,…,SN-1)∈,p是Fq特征,其中N=pvn,gcd(n,p)=1,那么N元的广义离散傅立叶变换是形如pv×n的矩阵,其中a是Fq扩域上的n次本原单位根.SN(x)是定义在序列(s0,s1,…,sN-1)∞上的多项式.为了研究N周期序列的线性复杂度与(广义)离散傅立叶变换的关系,引入了下面的定义.定义3矩阵的Günther重量就是各列的贡献之和,其中每一列的贡献就是每一列从第一个非0元素到列的最后一个元素的元素数目.比如,下面的矩阵,其Günther重量为4+3+2+2=11.引理1(Günther-Blahut定理)N周期序列S=(s0,s1,…,sN-1)∞,元素在有限域Fq上,域的特征是p,其中N=pvn,gcd(n,p)=1,那么该序列的线性复杂度等于SN=(s0,s1,…,sN-1)的广义离散傅立叶变换矩阵的Günther重量.推论1(Blahut定理)设gcd(N,p)=1,α是Fq扩域上的N次本原单位根,那么N周期序列S=(s0,s1,…,sN-1)∞的线性复杂度就是N元数组(SN(1),SN(α),…,SN(αN-1))的Hamming重量.为了研究序列的线性复杂度,需要研究该矩阵的结构性质.有如下引理.定义4设0≤j≤n-1,定义j关于g的模n的分圆陪集为Cj={j,jq,…,jqd-1},其中d是满足jqd≡j(modn)的最小正整数.引理2设gcd(n,p)=1,对于整数0≤j≤n-1,整数k满足0≤k≤n-1,是分圆陪集Cj中的元素,即k≡jqr(modn),整数r≥0.设|Cj|=lj,对于0≤t≤pv-1,有因此,广义离散傅立叶变换矩阵的结构依赖于模n的分圆陪集分布.假设Cj={j=k1,k2,…,},由上面的引理可知,对于广义离散傅立叶变换矩阵的一行而言,如果其元素同在一个分圆陪集中,那么要么同为0,要么同为非0,也就是说,对于同在一行的同一分圆陪集中的元素,其对Gunther重要贡献是一样的.设An=(a0,a1,…,an-1)是广义离散傅立叶变换矩阵的一行,有,或,对于1≤r≤lj.如果t=tj是最小的指标使得在第t行中有at,j≠0,于是就有pv-t行在的下面,所以分圆陪集Cj对广义离散傅立叶变换矩阵的贡献就是lj·(pv-t+1).从而,Günther-Blahut定理就可以推出N周期序列线性复杂度与分圆陪集的势的关系,于是有下面的结果.推论2N=pvn,有限域Fq的特征是p,gcd(n,p)=1.设是模n下的不同的分圆陪集,分别是这些分圆陪集的势,则Fq上N周期序列S的线性复杂度可以表示为因此,周期序列建立了与广义离散傅立叶变换矩阵的一一对应.为了研究周期序列的线性复杂度的分布情况,只要知道广义离散傅立叶变换矩阵的Günther重量分布的情况.2随机周期序列线性复杂度的渐近性质这一节里面,将对形如N=pvn,v≥0,gcd(n,p)=1的随机周期序列线性复杂度的方差进行计算.一般而言,只要知道了整数n的分圆陪集,理论上就可以计算线性复杂度的方差.这篇文章里,潜在的统计假设是N周期的序列分布是均匀的.定理1设N周期序列满足N=pvn,v≥0,元素定义在特征为p的有限域Fq上,gcd(n,p)=1,设D1,…,Dh是模n不同的分圆倍集,设mr=|Dr|,1≤r≤h,分别是这些分圆陪集的势,那么N周期随机周期序列线性复杂度的方差就是其中.证明因为VN,0=EN,0c2-(EN,0c)2,其中EN,0c2是线性复杂度平方的数学期望值,EN,0c是线性复杂度的期望值.在文献中,给出了线性复杂度的期望值.下面将先计算线性复杂度平方的数学期望值.由前面的引理可知,线性复杂度就是广义离散傅立叶变换矩阵的Gunther重量.对于每一个矩阵,Günther重量将被该矩阵的h列所确定,其中h是模n的分圆陪集的数目.设κ是pv×h的矩阵K的集合,u(c)是一列向量中第一个非0元素在该向量中所占的位置序数.可知每一个矩阵的Gunther重量为下面开始计算线性复杂度平方的数学期望值.这里利用公式代入上式,可以得到其中.从上可知类似的有因此,此外,从文献中知,因此文献中给出了计算周期为T=pmT1,gcd(p,T1)=1的序列的线性复杂度的方差的一个计算公式:其中Var[A()]表示方差,φ(d)表示小于d的正整数中与d互素的个数,nd表示q在中的阶数.这个计算公式的表达形式虽然与本文不同,但可以证明它们是等价的.不妨设N=T=pvn=pmT1,注意到f1(·),f2(·)是同一个函数,又其中li,1≤i≤s是不同的分圆陪集之势,φi是那些势为li的分圆陪集的元素总的个数.注意到这些势为li的分圆陪集的元素a都满足,其中gcd(n,q)=1.可知这些元素的gcd(a,n)都一样,于是.设,由群的性质可知这些元素都是乘法群中的元素,中的元素一共有φd个,从上可知φi=φ(d),li=nd,这里d为n的因子.于是VN,0=Var.下面利用本文的计算公式来确定某些重要周期的随机周期序列线性复杂度的方差,并且分析了随机周期序列线性复杂度的方差的渐近性质.定理2设有限域Fg的特征为p,gcd(N,p)=1,则Fq上N周期随机周期序列线性复杂度的方差为其中,mr是各分圆陪集的势,h是分圆陪集的数目.证明v=0代入定理1中.此时,这一结果可以作为判断这一类周期序列稳定性的度量指标.比如,(N,p)=1,q在上的阶数为d,可知有个分圆陪集的势为d,分圆陪集{0}的势为1.这一类随机周期序列线性复杂度的方差为特别情形下,g是上的本原根,d=N-1,于是从数论的角度,可以知道此周期序列的存在性.定理3设有限域Fq的特征为p,N=pv,则Fq上N周期随机周期序列线性复杂度的方差为证明此时只有C1={0}这一分圆陪集,a1=q-1.又由文献知,代入VN,0=EN,0c2-(EN,0c)2中可得结论.且易知,当q=2,N=2v时,可得VN,0=(2+2-N)(1-2-N)-21-NN.定理4设N周期序列,元素定义在特征为p的有限域Fq上,满足N=nk,k≥1,n是与p不同的奇素数.设d是q在域Fn中的阶数,满足qd=1+cn,c是与n互素的正整数.那么序列线性复杂度的方差为证明由文献可知,g在中的阶数为d,q在,i≥1中的阶数为dni.ZN中势为dnk-i,1≤i≤k的分圆陪集一共有个,势为1的分圆陪集有一个.由前面定理2可知化简可得结论.定理5设N周期序列,元素定义在特征为p的有限域Fq上,N=qn-1,n是素数,那么N周期随机周期序列线性复杂度的方差为证明因为分圆陪集的势r满足qr≡1(modqn-1),又n是素数,所以分圆陪集的势只能是1,n,于是可知N的分圆陪集只能为如下情形:{0}的势为1;个分圆陪集的势为n,那么从上面的结果就有即VN,0随着n的增加而近似线性增加.定理6设N周期序列,元素定义在特征为p的有限域Fq上,N=pvn,n为素