Fq上一类周期为2p2的四元广义分圆序列的线性复杂度

王 艳 相乃姣 韩西林 闫联陶

(西安建筑科技大学理学院 西安 710055)

1 引言

伪随机序列在流密码、扩频通信、雷达导航、全球定位等领域中都有着极为重要的应用[1]。伪随机序列的密码学性质，如周期性、相关性、线性复杂度、2-adic复杂度等直接影响着一个流密码算法的安全强度。其中线性复杂度是衡量伪随机序列性质的一个重要指标，根据Berlekamp-Massey(B-M)算法，若一个伪随机序列的线性复杂度大于其周期长度的1/2，则可称其为一个好的伪随机序列。

目前，已有大量的文献研究了广义分圆序列的线性复杂度。Ding[2]基于Whiteman广义分圆理论构造了一类周期为pq的2元广义分圆序列，并证明了这类序列具有高的线性复杂度和低的自相关性；Bai等人[3]基于Ding–Helleseth广义分圆理论构造了一类新的周期为pq的2元广义分圆序列，并确定了该类序列具有高的线性复杂度；李胜强等人[4]基于Whiteman广义分圆理论，通过选取不同的特征集，构造了一类新的周期为pq的2元广义分圆序列，得出该类序列的线性复杂度的下界为pq-p-q+1，并指出该类序列为平衡序列。Xiao等人[5]构造了一类新的周期为p2的2元广义分圆序列，计算出了该类序列具有高的线性复杂度，最后提出了一类新的周期为pm的2元广义分圆序列，并给出了一个关于其线性复杂度的猜想；随后Edemskiy等人[6]证明了这个猜想，并将其结果推广到了更一般的情形；Ouyang等人[7]基于Edemskiy等人的工作构造了两类周期为2pm的2元广义分圆序列，并给出了其线性复杂度的取值范围，结果表明这两类序列都具有好的线性复杂度性质。王艳等人[8]研究了一类新的周期为2pm的q阶2元广义分圆序列，并证明了该类序列具有高的线性复杂度；Wang等人[9]构造了F4上的一类周期为2pmqn的4元广义分圆序列，证明了该类序列的线性复杂度可以达到最大；Ke等人[10]构造了两类新的周期为2pm的4元广义分圆序列，分别确定了这两类序列在F4和Z4上都具有高的线性复杂度。Du等人[11]研究了F4上的周期为2p的4元广义分圆序列的线性复杂度，结果表明其最小值为p+1；Chen等人[12]确定了Z4上 的周期为2p的4元广义分圆序列的线性复杂度，结果表明其最小值为p；杜小妮等人[13]在Chen的基础上进行了推广，给出了Z4上周期为2p2的4元广义分圆序列的线性复杂度，结果表明该类序列具有好的线性复杂度性质。本文基于文献[13]构造的序列，构造了一类Fq上的周期为2p2的 4元广义分圆序列，并计算了该类序列在Fq上的极小多项式和线性复杂度。本文结构安排如下：第2节给出了Fq上 一类周期为2p2的4元广义分圆序列；第3节确定了该类序列在Fq上的极小多项式和线性复杂度；第4节对文章的工作做了小结和展望。

2 基础知识

设p是奇素数，g是奇数，且g是模p,2p,p2和2p2的公共本原元。记模2p2的剩余类环为Z2p2=

对i=0,1,令

3 主要结论及证明

3.1 主要定理及辅助引理

定理1设r为奇素数，且满足r ≥5,r/=p,m=ordp2(r)，并设β为扩域Frm上的2p2次单位根。由式(3)定义的周期为2p2的4 元广义分圆序列{s(t)}在Frm上的线性复杂度为

根据引理6、引理7和引理10知η0+η1=0，且η0η1=0，所以得η0=η1=0。 证毕

序列{s(t)}的生成多项式为

3.2 定理1的证明

注如果r|p-4且r|p-2，那么有p ≡4(modr),p≡2(modr)，则4≡2(modr),2≡0(modr)。因为r为奇素数，且r ≥5，所以这两种情况不同时发生。

通过使用Magma，我们计算下面的例子来验证本文的结果。

例1设p=5,g=3,r=7，则周期为50的4元广义分圆序列为003121213030312121303031222130-30312121303031212130。

由Magma计算得LC(s)=2p2-p+1=92，且r,p符合文中的第(1 2)种情况+p-2且2且r/|p-4且r/|p-2。

例2设p=7,g=3,r=5，则周期为98的4元广义分圆序列为0031312130202130313121302021 30313121302021303131223020213031312130202130 31312130202130313121302021。

由Magma计算得LC(s)=2p2-p+1=92，且r,p符合文中的第(4)种情况r|p-2。

例3设p=7,g=3,r=11，则由Magma计算得LC(s)=2p2=98,且r,p符合文中的第(12)种情况+p-2且2且r/|p-4且2。

例4设p=11,g=7,r=17，则周期为242的4元广义分圆序列为00302031303121202131213030 20313031212021312130302031303121202131213030 20313031212021312130302031303121202131213030 20313033212021312130302031303121202131213030 20313031212021312130302031303121202131213030 2031303121202131213030203130312120213121。

由Magma计算得LC(s)=2p2-1=241，且r,p符合文中的第(2)种情况r

例5设p=17,g=3,r=7，则周期为578的4元广义分圆序列为0031312130212020313020212031 21313030313121302120203130202120312131303031 31213021202031302021203121313030313121302120 20313020212031213130303131213021202031302021 20312131303031312130212020313020212031213130 30313121302120203130202120312131303031312130 21202031302021203121313030313121302120203330 20212031213130303131213021202031302021203121 31303031312130212020313020212031213130303131 21302120213020212031213130303131213021202031 30202120312131303031312130212020313020212031 21313030313121302120203130202120312131303031 31213021202031302021203121313030313121302120 20313020212031213130。

由Magma计算得LC(s)=2p2-2=576，且r,p符合文中的第(5)种情况r|3p2+p-2且r|p2-2。

4 结束语

本文基于杜小妮等人[13]的工作，构造了一类周期为2p2的4元广义分圆序列，研究了这类序列在Fq上的极小多项式和线性复杂度。结果表明，这类序列在Fq上的线性复杂度的最小值为2p2-p-1，大于其周期的1/2，即这类序列有高的线性复杂度，能够有效地抵抗B-M算法的攻击。后期研究该类序列4-adic复杂度也将是有意义的工作。