周期pq的二階廣義分圓二元序列的自相關(guān)值分布和2-adic復(fù)雜度

荊曉燕, 強(qiáng)詩(shī)瑗, 楊名慧, 馮克勤

(1.西北大學(xué) 數(shù)論及其應(yīng)用研究中心,陜西 西安 710127; 2.四川大學(xué) 數(shù)學(xué)學(xué)院,四川 成都 610064;3.中國(guó)科學(xué)院信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100084; 4.清華大學(xué) 數(shù)學(xué)系,北京 100093)

0 引 言

設(shè)p和q為2個(gè)不同的素?cái)?shù),pq=/pq.環(huán)pq的單位群為

*pq={a(modpq):gcd(a,pq)=1}=

{ip+jq(modpq):1≤i≤q-1,1≤j≤p-1}.

(1)

CS(0)=n稱為S的平凡自相關(guān)值.對(duì)于許多通信應(yīng)用,如雷達(dá)測(cè)距、CDMA通信系統(tǒng)和在流密碼加密中生成密鑰流序列,需要二元序列S的所有非平凡自相關(guān)值CS(τ)(1≤τ≤n-1)的絕對(duì)值|CS(τ)|越小越好.線性反饋移位寄存器(LFSR)和帶進(jìn)位的反饋移位寄存器(FCSR)是2種快速密鑰流生成器.序列的線性復(fù)雜度(2-adic復(fù)雜度)定義為可以生成該序列的最短LFSR(CSR)的長(zhǎng)度.根據(jù)Berlekamp-Massey算法[1](或有理近似算法[2]),在密碼學(xué)中安全的序列,其線性復(fù)雜度(2-adic復(fù)雜度)應(yīng)該超過其周期的一半.

表1 二元序列S(a,b,c)的自相關(guān)值Tab.1 The autocorrelation of the sequences S(a,b,c)

文獻(xiàn)[3-5]計(jì)算了序列S=S(1,0,0)的自相關(guān)值.特別地,當(dāng)q=p+2時(shí),序列S=S(1,0,0)具有理想自相關(guān),即對(duì)所有1≤τ≤pq-1,都有CS(τ)=-1.當(dāng)q=p+4時(shí),序列S=S(1,0,0)具有最優(yōu)3值自相關(guān),即對(duì)所有1≤τ≤pq-1,都有CS(τ)=1或-3.本文計(jì)算了當(dāng)(a,b,c)∈{0,1}3時(shí)序列S=S(a,b,c)的自相關(guān)值,并發(fā)現(xiàn)了序列S另外2種具有最優(yōu)自相關(guān)的情況,如表 1所示.

文獻(xiàn)[6-7]和[8-12]分別給出了二元序列S=S(1,0,0)的線性復(fù)雜度和2-adic復(fù)雜度.作為比較,表2中列出了本文和之前的相關(guān)結(jié)果.

表2 二元序列S(a,b,c)的2-adic復(fù)雜度Tab.2 The 2-adic complexity of the sequences S(a,b,c)

其中l(wèi)o表示l的奇數(shù)部分,ep=(-1)a+c-(-1)a+b,eq=(-1)b+c-(-1)a+b.

1 自相關(guān)值分布

這一節(jié)確定由引言(1)中定義的周期為n=pq的二元序列S=S(a,b,c)(對(duì)所有(a,b,c)∈{0,1}3)的自相關(guān)值分布

CS(τ)(0≤τ≤n-1).

設(shè)R=[Г],其中Г=〈x|xn-1〉={1Г,x,x2,…,xn-1}為由x生成的階為n=pq的乘法循環(huán)群.對(duì)Г的一個(gè)子集S,將S看成群環(huán)[Г]中的元素∑g∈Sg.令

有

另一方面,由(1)式二元序列S=S(a,b,c)的定義可得,

其中

因此

S(x)=e·1Г+(-1)aГp+(-1)bГq+Gp(x)Gq(x)=

H+Gp(x)Gq(x),

(2)

其中e=(-1)c-(-1)a-(-1)b∈,H=e+(-1)aГp+(-1)bГq.

因?yàn)棣摇莽ぁ?σ(g)=g-1是群Г的自同構(gòu),所以有σ(Гp)=Гp,σ(Гq)=Гq并且

由(2)得

(3)

為了計(jì)算S(x)S(x-1)在R中的值,將利用如下引理,此引理中Gp(x)與Gq(x)分別可以看作取值于R中的p與q上二次高斯和版本.

引理1在群環(huán)R=[Г]中,有

B) ГpGq(x)=ГqGp(x)=0,ГpГq=Г.

證A) 由Gp(x)的定義,有

類似地,有ГqGp=0.

根據(jù)引理1與(2),(3)可得

(4)

并且

H2=(e·1Г+(-1)aГp+(-1)bГq)2(e=(-1)c-(-1)a-(-1)b)=

e2·1Г+ГpГp+ГqГq+2(e(-1)aГp+e(-1)bГq+(-1)a+bГpГq)=

e2·1Г+qГp+pГq+2(e(-1)aГp+e(-1)bГq+(-1)a+bГ)

(ГpГp=|Гp|·Гp=qГp),

HGp(x)Gq(x)=eGp(x)Gq(x),

(p·1Г-Гq)(q·1Г-Гp)=pq·1Г-pГp-qГq+Г,

則(4)變?yōu)?/p>

S(x-1)S(x)=(pq+e2)·1Г+(q-p+2e(-1)a)Гp+(p-q+2e(-1)b)Гq+

(5)

Г=1Г+(Гp-1Г)+(Гq-1Г)+Г*,

S(x-1)S(x)=pq+(q-p+2e(-1)a)(Гp-1Г)+(p-q+2e(-1)b)(Гq-1Г)+

(1+2(-1)a+b)[(Гp-1Г)+(Гq-1Г)+Г*]+

pq+(q-p+2(-1)a+c-1)(Гp-1Г)+(p-q+2(-1)b+c-1)(Гq-1Г)+

因此可得2元序列S=S(a,b,c)的如下自相關(guān)分布結(jié)果:

定理1令(a,b,c)∈{0,1}3,S=S(a,b,c)為由(1)定義的周期為n=pq的二元序列,則對(duì)0≤τ≤n-1,有

A.1) 如果q=p+2,(a,b,c)=(1,0,0)或(0,1,1),序列S=S(a,b,c)是理想自相關(guān)序列,即

Cs(τ)=-1對(duì)所有1≤τ≤n-1.

A.2) 如果q=p+2,(a,b,c)=(0,0,0)或(1,1,1),序列S=S(a,b,c)的自相關(guān)值為Cs(τ)=-1或3對(duì)所有1≤τ≤n-1.

2 2-adic復(fù)雜度

這一節(jié)將確定二元序列S=S(a,b,c)(對(duì)所有(a,b,c)∈{0,1}3)的2-adic復(fù)雜度的精確值.

其中d=gcd(T(2),2n-1).

取x=2,有

2T(2)≡-S(2)+2n-1=-S(2)(mod2n-1).

因此d=gcd(T(2),2n-1)=gcd(S(2),2n-1).對(duì)于在R中的式(2),取x=2可得

(6)

其中e=(-1)c-(-1)a-(-1)b,

類似地,在(3)中取x=2,可得

(7)

引理21) d*=1,dp=gcd(e+(-1)aq,2p-1),dq=gcd(e+(-1)bq,2q-1),其中

e=(-1)c-(-1)a-(-1)b.

2) 如果4p>q+1,則dp=1.如果4q>p+1,則dq=1.

3) d(=gcd(S(2),2n-1))=max(dp,dq).特別地,如果16p>4q+4>p+5,則d=1,并且二元序列S=S(a,b,c)有最大2-adic復(fù)雜度log2(2pq-1).

證1) 首先證明d*=1.由(6)可得

在引理1中令x=2可得

類似地,有

0≡S(2)≡e+Gp(2)Gq(2)(modπ).

由此可得

(8)

這意味著π|pq±e2,其中e2=1或9.

可得π=q.接下來(lái)由π|pq±e2可得π|e.因此π=3.另外,因?yàn)閜,q和n=pq都是奇數(shù),所以有下式

下面計(jì)算dp=gcd(S(2),2p-1).由(6)可得

因?yàn)?/p>

所以S(2)≡e+(-1)aq(mod2p-1),dp=gcd(S(2),2p-1)=gcd(e+(-1)aq,2p-1).類似可得dq=gcd(e+(-1)bp,2q-1).

因此4p≤2π-2≤q+3-2=q+1.由此可知,當(dāng)4p>q+1時(shí),dp=1.類似地,當(dāng)4q>p+1時(shí),dq=1.

3) 由d*=1以及gcd(2p-1,2q-1)=1可得

d=gcd(S(2),2n-1)=gcd(S(2),(2p-1)(2q-1))=gcd(S(2),2p-1).gcd(S(2),2q-1)=dpdq.但是4p≤q+1和4q≤p+1不能同時(shí)成立.由此可知dp=1或dq=1.因此d=max(dp,dq).

綜上,可得下述定理.

定理2令(a,b,c)∈{0,1}3,S=S(a,b,c)是由(1)定義的周期為n=pq的二元序列,則

A) 序列S的2-adic復(fù)雜度為

其中dp=gcd(q-1+(-1)a+c-(-1)a+b,2p-1),dq=gcd(p-1+(-1)b+c-(-1)a+b,2q-1).

B) 當(dāng)4p>q+1時(shí),有dp=1.當(dāng)4q>p+1時(shí),有dq=1.特別地,如果16p>4q+4>p+5,則對(duì)所有(a,b,c)∈{0,1}3,序列S(a,b,c)的2-adic復(fù)雜度都達(dá)到最大值log2(2n-1).

注記2在引言中列出了理想或最優(yōu)自相關(guān)序列S=S(a,b,c)的參數(shù),對(duì)于這些序列,有q=p+2或p+4,因此p和q滿足16p>4q+4>p+5.由定理2之B)可得,這些序列的2-adic復(fù)雜度都達(dá)到最大值log2(2pq-1).