一類平衡的廣義割圓序列的二進(jìn)制復(fù)雜度研究*

趙春娥,孫玉花,閆統(tǒng)江

1.中國(guó)石油大學(xué)(華東)理學(xué)院,青島266580

2.應(yīng)用數(shù)學(xué)福建省高校重點(diǎn)實(shí)驗(yàn)室(莆田學(xué)院),莆田351100

3.齊魯工業(yè)大學(xué)(山東省科學(xué)院),山東省計(jì)算中心(國(guó)家超級(jí)計(jì)算濟(jì)南中心),山東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室,濟(jì)南250014

1 引言

具有良好統(tǒng)計(jì)特性的偽隨機(jī)序列被廣泛應(yīng)用于密碼學(xué)和通信系統(tǒng).二進(jìn)制復(fù)雜度是衡量序列偽隨機(jī)性質(zhì)的一個(gè)重要指標(biāo),Klapper 在1997年提出二進(jìn)制復(fù)雜度的概念[1],并指出任何一個(gè)二元序列都可以由帶進(jìn)位的反饋移位寄存器(FCSR)生成,他將二進(jìn)制復(fù)雜度定義為生成序列的最短FCSR 的級(jí)數(shù).同時(shí)Klapper 又給出針對(duì)二進(jìn)制復(fù)雜度的有理逼近算法(RAA),該算法要求安全的密鑰流序列的二進(jìn)制復(fù)雜度不小于其周期的一半,所以計(jì)算密鑰流序列的二進(jìn)制復(fù)雜度是一項(xiàng)重要的研究課題.此外,Klapper還指出具有質(zhì)數(shù)周期的m-序列具有極大二進(jìn)制復(fù)雜度.2010年,Tian和Qi 證明了所有二元m-序列的二進(jìn)制復(fù)雜度都是極大的[2].2014年,Xiong 等人提出了一種利用循環(huán)矩陣來(lái)計(jì)算二元序列的二進(jìn)制復(fù)雜度的新方法,并用此方法證明了所有已知的具有理想2 值自相關(guān)的序列具有極大的二進(jìn)制復(fù)雜度[3].隨后,胡紅鋼用另一種簡(jiǎn)捷的方法證明了這一結(jié)論[4].此后這兩種方法被廣泛應(yīng)用在序列的二進(jìn)制復(fù)雜度求解中.例如,Xiong 等人證明了具有最優(yōu)自相關(guān)的Legendre 序列、Ding-Helleseth-Lam 序列和另外兩類基于交織結(jié)構(gòu)的序列也具有極大的二進(jìn)制復(fù)雜度[3,5],曾祥勇、孫玉花、Winterhof 等人分別研究了幾類廣義割圓序列的二進(jìn)制復(fù)雜度[6–8].本文研究一類2 階的pq周期的Whiteman 廣義割圓序列的二進(jìn)制復(fù)雜度,這類序列由Ding和Helleseth 給出[9],具有最優(yōu)的平衡性,而白恩健等人則證明了這類序列具有很高的線性復(fù)雜度[10].

2 一類Whiteman 廣義割圓序列及序列的二進(jìn)制復(fù)雜度定義

設(shè)N=pq,其中p,q是互不相同的奇素?cái)?shù),滿足p

存在唯一解x.令e=(p?1)(q?1)/2,定義集合

則稱它們?yōu)閆N上關(guān)于素?cái)?shù)p和q的2 階Whiteman 廣義割圓類.Whiteman 已經(jīng)證明[8]

并稱4 個(gè)交集的元素個(gè)數(shù)(i,j)=|(Di+1)∩Dj|(其中i=0,1;j=0,1)為相應(yīng)的廣義割圓數(shù),其中Di+1={x+1|x∈Di}.令

該序列由Ding和Helleseth 給出[9],白恩健等人則證明了這類序列具有很高的線性復(fù)雜度[10].

定義1令N是一個(gè)正整數(shù)是一個(gè)周期為N的二元序列,令若

由上面的式(2)可以看出,φ2(s)可通過(guò)式(3)求出:

本文研究q=p+4時(shí)序列的二進(jìn)制復(fù)雜度,并給出此時(shí)序列的二進(jìn)制復(fù)雜度的一個(gè)下界.因此,如無(wú)特別說(shuō)明,后文將總假定p和q滿足gcd(p?1,q?1)=2,q=p+4,從而此時(shí)必有q≡p≡3 mod 4.

3 一類Whiteman 廣義割圓序列的二進(jìn)制復(fù)雜度

引理 1[3]是周期為N的二元序列,A=(aij)N×N是一個(gè)N階矩陣,其中aij=S(j?i)modN,則

(2)如果det(A)=0,則gcdS(2),2N?1gcd(det(A),2N?1).

結(jié)合上節(jié)式(3)中φ2(s)的表達(dá)式和引理1 中的(2)可以看出,如果求出行列式det(A)的值,就能分析出φ2(s)的一個(gè)下界.為了計(jì)算det(A)的值,需要下面一系列引理.

引理2[11]對(duì)于任何一個(gè)a∈ZN和B?ZN,記aB={ab|b∈B},則有以下性質(zhì)

(1)對(duì)于每一個(gè)固定的a∈Di,有aP=P,aQ=Q,且aDj=D(i+j)mod2,其中i,j=0,1.

(2)對(duì)于每一個(gè)固定的a∈P,如果b取遍Di中的每個(gè)元素時(shí),則元素ab恰好取到P中每一個(gè)元素次,并且aP=P,aQ=R.

(3)對(duì)于每一個(gè)固定的a∈Q,如果b取遍Di中的每個(gè)元素時(shí),則元素ab恰好取到Q中每一個(gè)元素次,并且aQ=Q,aP=R.

定義2[6]令p,q是滿足gcd(p?1,q?1)=2 的兩個(gè)奇素?cái)?shù),N=pq,Dj如前所述,令是復(fù)數(shù)域上一個(gè)N次本原單位根,則稱為基于2 階割圓類的高斯周期,其中j=0,1.

引理3[6]令gcd(p?1,q?1)=2,p≡3(mod4),q≡3(mod4),ηi是如上定義的基于Di的高斯周期,其中i=0,1,則有

引理4[7]令p≡3 mod 4 為奇素?cái)?shù),記則

引理5令p≡3 mod 4,q≡3 mod 4 為奇素?cái)?shù),若為整數(shù),則

證明:由引理4 知分別互為共軛復(fù)數(shù),令而由的值可知因此,四種組合如下必為整數(shù):

把D0,D1進(jìn)一步劃分如下:

則D0=D00∪D01,D1=D10∪D11.

定理1設(shè)為式(1)所定義的二元序列,限定p,q是滿足gcd(p?1,q?1)=2,q=p+4 的奇素?cái)?shù),則

證明:由引理2,則

(1)a∈R時(shí),

類似地,可以得到

(6)a∈D00時(shí),

(7)a∈D01時(shí),

(8)a∈D10時(shí),

(9)a∈D11時(shí),

定理2設(shè)為式(1)所定義二元序列,并限定p,q是滿足gcd(p?1,q?1)=2,q=p+4 的奇素?cái)?shù),則

證明:由引理1和定理1 得

注意到p≡q≡3 mod 4,由引理3–4 得

將其代入得

又因?yàn)閝=p+4,所以

引理6[6]令p和q是互不相同的奇素?cái)?shù),并且N=pq,則且特別地,如果p

定理3設(shè)為式(1)所定義的二元序列,并限定p,q是滿足gcd(p?1,q?1)=2,q=p+4的奇素?cái)?shù),則的二進(jìn)制復(fù)雜度滿足φ2(s)≥pq?p?q?1.

證明:根據(jù)定理2

由引理1 的(2),我們需要分析gcd(det(A),2N?1).下面依次分析上述行列式表達(dá)式中每一項(xiàng)因子和2N?1 的公因子。

令r是2N?1 的任意一個(gè)素因子,Ordr(2)是模r的乘法階,則2Ordr(2)≡1 modr,因此r|2Ordr(2)?1,又由r|2N?1,可得Ordr(2)|N.特別地,對(duì)于N=p(p+4),則Ordr(2)=p(p+4),p或p+4.下面我們將分三種情況來(lái)證明gcd(det(A),2N?1)≤(2p?1)(2p+4?1).

? Ordr(2)=p(p+4).根據(jù)費(fèi)馬小定理,r|2r?1?1,因此Ordr(2)≤r?1.由于Ordr(2)=p(p+4),所以,我們有p(p+4)≤r?1,即r≥p(p+4)+1,而式(5)中前三個(gè)因式都滿足因此前三項(xiàng)都與2N?1 互素,而對(duì)于最后一個(gè)因子項(xiàng)來(lái)說(shuō),由費(fèi)馬小定理可知Ordr(2)|r?1,那么有pq|r?1,令r=kpq+ 1.若即pq(pq+2p+2q?10)+4q+9=16ktpq+16t.若16t

? Ordr(2)=p.由于Ordr(2)≤r?1,因此p≤r?1,所以因此由于2p≡1 modr,因此r|2p?1.由于gcd(r,p+4)=1,根據(jù)引理6,因此gcd(det(A),2N?1)|2p?1.

? Ordr(2)=p+4.顯然r|2p+4?1.由引理6,1.因此gcd(det(A),2N?1)|2p+4?1.

綜合三種情況,可知gcd(det(A),2N?1)|(2p?1)(2p+4?1),且1.這說(shuō)明gcd(det(A),2N?1)≤(2p?1)(2p+4?1),由引理1

最后,根據(jù)二進(jìn)制復(fù)雜度的定義,我們得到

4 結(jié)論

本文對(duì)一類平衡的廣義分圓序列的二進(jìn)制復(fù)雜度進(jìn)行研究,此類序列之前已經(jīng)被證明了具有很高的線性復(fù)雜度足以抵抗線性攻擊.本文的結(jié)果表明此序列同樣具有較高的二進(jìn)制復(fù)雜度,也足以抵抗針對(duì)帶進(jìn)位的線性反饋移位寄存器(FCSR)所提出的有理逼近算法(RAA)的攻擊.