王艷，李順波，薛改娜

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

1 引言

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

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

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

2 基礎(chǔ)知識

2.1 SLCE 序列

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

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

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

若q≡ 3(mod 4)，則有

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

稱序列{si}為SLCE 序列。這個定義等價于

也等價于

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

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

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

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

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

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

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

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

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

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

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

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

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

巧合的是，2N-1=MN恰為第N個Mersenne數(shù)，當(dāng)MN為 Mersenne 素 數(shù) 時，有g(shù)cd(S(2),2N-1)=1，即序列s的極小連接整數(shù)為Mersenne 素數(shù)時，其2-adic 復(fù)雜度達(dá)到最大。迄今，已發(fā)現(xiàn)的Mersenne 素數(shù)有51 個，分別為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個Mersenne 數(shù)為素數(shù)的必要條件是N為素數(shù)，因而對素數(shù)周期序列，當(dāng)周期N滿足2N-1 為素數(shù)時，序列2-adic 復(fù)雜度達(dá)到最大。

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

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

設(shè){si},i=0,1,…,n-1，為二元序列，稱函數(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ù)滿足

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

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

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

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

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

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

由引理1 和式(1)可得

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

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

若τ∈4A，則有

于是

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

對應(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)時，在τ=1,2,…,q-2中有個數(shù)使AC(τ)=-4 。

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

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

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

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

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

證畢。

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

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

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

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

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

證畢。

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

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

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

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

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

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

則有

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

其中，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)時，有

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

例q=43時，F(xiàn)43上的本原元分別對應(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 驗證發(fā)現(xiàn)，F(xiàn)43中的所有SLCE 序列都達(dá)到最大2-adic 復(fù)雜度。類似地，F(xiàn)7、F19、F31、F47等域上的SLCE 序列都可達(dá)到最大2-adic 復(fù)雜度。但等域上的SLCE 序列都滿足gcd(S(2),2N-1)=3。盡管沒有達(dá)到最大2-adic復(fù)雜度，但由可知，在N＞4 時,這樣的SLCE 序列仍有很高的2-adic 復(fù)雜度。

5 結(jié)束語

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