SLCE 序列的2-adic 復(fù)雜度

王艷，李順波，薛改娜

（西安建筑科技大學(xué)理學(xué)院，陜西 西安 710055）

1 引言

周期偽隨機(jī)序列在通信和密碼領(lǐng)域有著廣泛的應(yīng)用。有關(guān)周期序列的自相關(guān)性、線(xiàn)性復(fù)雜度及2-adic 復(fù)雜的研究一直是序列研究的熱點(diǎn)。

周期序列可以由線(xiàn)性移位寄存器(LFSR，linear feedback shift register)生成，也可以由帶進(jìn)位的移位寄存器(FCSR，feedback with carry shift register)生成。生成序列的最短LFSR 的級(jí)數(shù)稱(chēng)為該序列的線(xiàn)性復(fù)雜度，生成序列的最短FCSR 的級(jí)數(shù)稱(chēng)為該序列的2-adic 復(fù)雜度。由B-M (Berlekamp-Massey)算法和有理逼近算法可知，獲得連續(xù)2 倍線(xiàn)性復(fù)雜度或2 倍2-adic 復(fù)雜度長(zhǎng)的序列，便可以恢復(fù)生成該序列的LFSR 或FCSR，因此，周期序列的設(shè)計(jì)要求高線(xiàn)性復(fù)雜度、高2-adic 復(fù)雜度。同時(shí)，序列的自相關(guān)性也是衡量序列的一個(gè)重要指標(biāo)，好的序列應(yīng)該有低的自相關(guān)值。

SLCE (Sidelnikov-Lempel-Cohn-Eastman)序列是一類(lèi)偶周期分圓序列，由Sidelnikov[1]首次提出，故有文獻(xiàn)稱(chēng)該類(lèi)序列為Sidelnikov 序列；Lempel、Cohn 和Eastman[2]研究了該類(lèi)序列的自相關(guān)性，使該序列受到關(guān)注，因而很多文獻(xiàn)中以這4 人的姓名首字母的縮寫(xiě)（SLCE）命名這種分圓序列。SLCE序列的線(xiàn)性復(fù)雜度一度是一個(gè)難題，Kyureghyan 等[3]發(fā)現(xiàn)SLCE 序列的線(xiàn)性復(fù)雜度與一類(lèi)分圓數(shù)的余數(shù)及 Jacobsthal 和有關(guān)，推進(jìn)了此項(xiàng)研究工作。Helleseth 等[4-5]給出了p=3,5,7 時(shí)，周期為pm-1 序列的線(xiàn)性復(fù)雜度；Meidl 等[6]利用分圓數(shù)確定了某些具體序列的線(xiàn)性復(fù)雜度。之后關(guān)于SLCE 序列1-錯(cuò)線(xiàn)性復(fù)雜度[7]、線(xiàn)性復(fù)雜度的界[8-9]、特征值[10]等研究陸續(xù)出現(xiàn)?；谶@些研究，SLCE 序列的2-adic 復(fù)雜度也成了一個(gè)有意義的問(wèn)題，本文主要研究SLCE 序列的2-adic 復(fù)雜度。

2 基礎(chǔ)知識(shí)

2.1 SLCE 序列

設(shè)q為奇素?cái)?shù)p的冪，即q=pm，記Fq為q元有限域，α為Fq的本原元，即Fq的乘法群的生成元。定義中的二次特征為

設(shè)q=df+ 1，〈αd〉為由αd生成的乘法子群，稱(chēng)陪集為關(guān)于Fq的d階分圓陪集。顯然此處依賴(lài)于α的選擇，于是有

引理1[11]若q≡ 1(mod4)，則有

若q≡ 3(mod 4)，則有

由前述記號(hào)，在上定義周期為(q-1)的SLCE序列{si}如式(1)所示。

稱(chēng)序列{si}為SLCE 序列。這個(gè)定義等價(jià)于

也等價(jià)于

根據(jù)式(2)，在有限域F31中取本原元α=3，d=2，則有

進(jìn)而可得一個(gè)周期為30 的SLCE 序列如式(5)所示。

2.2 FCSR 和序列的2-adic 復(fù)雜度

考慮到線(xiàn)性移位寄存器容易被攻擊的問(wèn)題，Klapper 等[12]提出了自帶進(jìn)位的反饋移位寄存器(FCSR)。FCSR 由r個(gè)系數(shù)qi(i=1,2,…,r）∈(0,1),qr=1，以及一個(gè)初始存儲(chǔ)整數(shù)mn-1(可為任意整數(shù))確定，結(jié)構(gòu)如?圖1 所示。

圖1 FCSR 結(jié)構(gòu)

記FCSR 的任意一個(gè)狀態(tài)為 (an-1,an-2,…,ai,…,an-r)(ai∈{ 0,1},i=n-1,n-2,…,n-r)，存儲(chǔ)整數(shù)為mn-1，其運(yùn)算如下。

2)右移一位，輸出最右端的an-r。

3)將a n=δn(mod2)放入FCSR 最左端。

每一個(gè)最終周期序列都可以由一個(gè) FCSR 產(chǎn)生。反過(guò)來(lái)，所有由FCSR 生成的序列也都是最終周期序列[12]。設(shè)為最終周期序列，q為生成的FCSR 的連接整數(shù)，則稱(chēng)q為的極小連接整數(shù)，極小連接整數(shù)整除任意連接整數(shù)。FCSR 序列的周期完全由其極小連接整數(shù)確定。類(lèi)似于線(xiàn)性復(fù)雜度，2-adic 復(fù)雜度衡量一個(gè)周期序列需要用多大周期的FCSR 來(lái)生成，定義如下。

定義 1[12]設(shè)s={si}為嚴(yán)格周期序列，其中，q為序列s的極小連接數(shù)，整數(shù)p滿(mǎn)足gcd(p,q)=1，稱(chēng)實(shí)數(shù)?(s)=lbq為序列s的2-adic 復(fù)雜度。

2-adic 復(fù)雜度衡量一個(gè)二元序列由帶進(jìn)位的移位寄存器(FCSR)[12-13]生成的難度，它與線(xiàn)性復(fù)雜度沒(méi)有必然聯(lián)系。具有高線(xiàn)性復(fù)雜度的序列的2-adic復(fù)雜度可能會(huì)很低，反之亦然。Klapper 和Goresky[12]提出了有理逼近算法，即對(duì)于一條固定序列，只要已知其約為2-adic 復(fù)雜度個(gè)位置上的元素的2 倍，就能唯一確定原序列。這就要求密鑰序列必須具有高的2-adic 復(fù)雜度，才能有效抵抗有理逼近攻擊。

設(shè)s為嚴(yán)格周期序列，記則有，故

當(dāng)gcd(S(2),2N-1)=1時(shí)，?(s)達(dá)到最大值l b(2N-1)≈N。

巧合的是，2N-1=MN恰為第N個(gè)Mersenne數(shù)，當(dāng)MN為 Mersenne 素 數(shù) 時(shí)，有g(shù)cd(S(2),2N-1)=1，即序列s的極小連接整數(shù)為Mersenne 素?cái)?shù)時(shí)，其2-adic 復(fù)雜度達(dá)到最大。迄今，已發(fā)現(xiàn)的Mersenne 素?cái)?shù)有51 個(gè)，分別為N=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1 279,2 203,2 281,3 217,4 253,4 423,9 689,9 941,11 213,19 937,21 701,23 209,44 497,86 243,110 503,132 049,216 091,756 839,859 433,1 257 787,1 398 269,2 976 221,3 021 377,6 972 593,13 466 917,20 996 011,24 036 583,25 964 951,30 402 457,32 582 657,37 156 667,42 643 801,43 112 609,57 885 161,74 207 281,77 232 917,82 589 933。由于第N個(gè)Mersenne 數(shù)為素?cái)?shù)的必要條件是N為素?cái)?shù)，因而對(duì)素?cái)?shù)周期序列，當(dāng)周期N滿(mǎn)足2N-1 為素?cái)?shù)時(shí)，序列2-adic 復(fù)雜度達(dá)到最大。

對(duì)一般周期序列，2-adic 復(fù)雜度由gcd(S(2),2N-1)確定，這依賴(lài)于序列本身的性質(zhì)。Tian 等[13]研究了m序列的2-adic 復(fù)雜度，利用m序列極小多項(xiàng)式的特征，推導(dǎo)出m序列可以達(dá)到最大2-adic 復(fù)雜度。Xiong 等[14]通過(guò)對(duì)周期序列的循環(huán)行列式非奇異性的研究，指出任何周期為N的理想二值自相關(guān)序列的2-adic 復(fù)雜度就是N，該結(jié)果覆蓋了文獻(xiàn)[13]的結(jié)果。Hu 等[15]對(duì)文獻(xiàn)[14]的結(jié)果給出了一個(gè)簡(jiǎn)化的證明，給出了獲得周期序列2-adic 復(fù)雜度的新方法。

3 SLCE 序列的自相關(guān)性

設(shè){si},i=0,1,…,n-1，為二元序列，稱(chēng)函數(shù)

為該序列的自相關(guān)函數(shù)。周期為n的序列{si}的自相關(guān)函數(shù)可用差集表示為[16]

其中，集合C={i|si=1,i=0,1,…,n-1}為序列{si}的支撐集。

由于SLCE 序列為周期為(q-1)的平衡序列，其自相關(guān)函數(shù)滿(mǎn)足

自相關(guān)函數(shù)值反映了序列在移位τ后，與原序列的接近程度。實(shí)際應(yīng)用中希望序列的自相關(guān)函數(shù)值盡可能小。

設(shè)q為奇素?cái)?shù)的冪，即q=pm，記Fq為q元有限域，α乘法群的本原元。記

定理1設(shè){si}是周期為(q-1)的SLCE 序列，則

1)當(dāng)q≡ 1(mod4)時(shí)，

2)當(dāng)q≡ 3(mod4)時(shí)，

證明根據(jù)式(1)，需計(jì)算|(τ+C)∩C|，定義αC={αi:i∈C}=D1-1，及αC+τ=ατ(D1-1)，則有

由引理1 和式(1)可得

1)當(dāng)q≡ 1(mod4)時(shí)，若τ∈A1∪A2∪A3，則有

對(duì)應(yīng)的|(τ+C)∩C|分別等于二階分圓數(shù)(1,1)2、(1,0)2和 (0,1)2，且都等于根據(jù)式(6)有

若τ∈4A，則有

于是

2)當(dāng)q≡ 3(mod4)時(shí)，若τ∈A1∪A2∪A4，則有

對(duì)應(yīng)的|(τ+C)∩C|分別等于 (1,1)2、(1,0)2和(0,0)2，且都等于。根據(jù)式(6)有

若τ∈3A，則有

于是

證畢。

定理1 表明SLCE 序列是3 值自相關(guān)序列。

推論1設(shè){si}是周期為q-1的SLCE 序列，則

1)當(dāng)q≡ 1(mod4)時(shí)，在τ=1,2,…,q-2中有個(gè)數(shù)使AC(τ)=-4 。

2)當(dāng)q≡ 3(mod4)時(shí)，在τ=1,2,…,q-2中有的數(shù)使AC(τ)=2。

由分圓數(shù)的取法可證明推論1。

定義2若序列{si}、{tj}均為周期為N的序列，并且在一個(gè)周期上有si=tN-1-i,i=0,1,…,N-1，則稱(chēng){si}、{tj}為互反序列。

定理2記?為歐拉函數(shù)，域Fq中共有?(q-1)個(gè)SLCE 序列，并成對(duì)為互反序列。

證明由qF中本原元的個(gè)數(shù)為?(q-1)可得,由于在有限域中，當(dāng)α為本原元時(shí)，α-1也為本原元，故?(q-1)個(gè)本原元成對(duì)出現(xiàn)。由于對(duì)本原元α，時(shí)，故α-1生成序列的第i個(gè)元與α生成序列的第(q-1-i)個(gè)元一樣，即為互反序列。

證畢。

定理3設(shè){si}是周期為(q-1)的SLCE 序列，則

1)當(dāng)q≡ 1(mod4)時(shí)，F(xiàn)q上的全部SLCE 序列共有個(gè)自相關(guān)譜。

2)當(dāng)q≡ 3(mod4)時(shí)，F(xiàn) q上的全部SLCE 序列共有個(gè)自相關(guān)譜。

證明記α為Fq的一個(gè)本原元，當(dāng)q≡1(mod4)時(shí)，-α也是Fq的一個(gè)本原元，且有，故α與α-生成序列的自相關(guān)譜相同。又由自相關(guān)函數(shù)的對(duì)稱(chēng)性及α與α-1生成序列為互反序列可知，α與α-1生成序列的自相關(guān)譜相同。于是α、-α、α-1、-α-1生成的序列同自相關(guān)譜。并且由其他本原元生成序列不同可得，當(dāng)q≡ 1(mod4)時(shí)，F(xiàn) q上的全部SLCE 序列共有個(gè)自相關(guān)譜。

當(dāng)q≡ 3(mod4)時(shí)，對(duì)本原元α、-α不是本原元，由前述知，此時(shí)Fq上的全部SLCE 序列共有個(gè)自相關(guān)譜。

證畢。

下面研究SLCE 序列的2-adic 復(fù)雜度。

4 SLCE 序列的2-adic 復(fù)雜度

定理4設(shè){si}是周期為(q-1)的SLCE 序列，則

1)當(dāng)q≡1(mod4)時(shí)，

2)當(dāng)q≡ 3(mod4)時(shí)，

證明設(shè){si}為SLCE 序列，記Z[x]多項(xiàng)式為

則有

當(dāng)x=2 時(shí)，有

其中，k為整數(shù)。于是

證畢。

推論2 設(shè)s={si}是周期為q-1的SLCE 序列，記，有

1)若q≡ 1(mod4)且

則s的2-adic 復(fù)雜度?(s)達(dá)到最大值。

2)若q≡ 3(mod4)，且

則s的2-adic 復(fù)雜度?(s)達(dá)到最大值。

推論2 的證明由定理4 易得。

進(jìn)一步，當(dāng)q≡ 1(mod4)時(shí)，有

當(dāng)q≡ 3(mod 4)時(shí)，有

例q=43時(shí)，F(xiàn)43上的本原元分別對(duì)應(yīng)3,29,5,26,12,18,19,34,20,28,30,33。由本原元3 生成的SLCE 序列為1,0,0,1,1,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,1,1,0,0,1,1,1,0,1,0,0,1。，且有

由本原元5 生成的SLCE 序列為1,0,1,0,0,1,0,0,0,0,0,0,1,1,1,0,0,1,1,0,1,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,0,0,0,1,1,1,，且有式(8)成立。

由本原元26 生成的SLCE 序列為1,1,1,1,0,0,0,1,0,1,0,1,1,0,1,1,0,0,1,1,1,0,1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,，且有式(8)成立。

由本原元29 生成的SLCE 序列為1,1,0,0,1,0,1,1,1,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,1,1,0,1,1,1,1,0,0],且有式(8)成立。

由Magma 驗(yàn)證發(fā)現(xiàn)，F(xiàn)43中的所有SLCE 序列都達(dá)到最大2-adic 復(fù)雜度。類(lèi)似地，F(xiàn)7、F19、F31、F47等域上的SLCE 序列都可達(dá)到最大2-adic 復(fù)雜度。但等域上的SLCE 序列都滿(mǎn)足gcd(S(2),2N-1)=3。盡管沒(méi)有達(dá)到最大2-adic復(fù)雜度，但由可知，在N＞4 時(shí),這樣的SLCE 序列仍有很高的2-adic 復(fù)雜度。

5 結(jié)束語(yǔ)

SLCE 序列已被證明具有高線(xiàn)性復(fù)雜度，其2-adic 復(fù)雜度取值成為有意義的問(wèn)題。本文通過(guò)SLCE 序列的自相關(guān)函數(shù)值研究了其2-adic 復(fù)雜度，給出了SLCE 序列可以達(dá)到最大2-adic 復(fù)雜度的一個(gè)充分條件，并舉例證明確實(shí)存在大量能達(dá)到條件的SLCE 序列，這些SLCE 序列能夠抵抗有理逼近攻擊，結(jié)合SLCE 序列高線(xiàn)性復(fù)雜度[3-6]可知，這些SLCE 序列是密碼學(xué)意義上的好的偽隨機(jī)序列。