吳晨煌，許春香，杜小妮

（1.電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，四川 成都 611731；2.莆田學(xué)院應(yīng)用數(shù)學(xué)福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 莆田 351100；3.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅 蘭州 730070）

1 引言

偽隨機(jī)序列的應(yīng)用領(lǐng)域非常廣泛，在通信、雷達(dá)導(dǎo)航、密碼學(xué)等領(lǐng)域都有極其重要的應(yīng)用。比如在流密碼中，偽隨機(jī)序列作為密鑰序列與明文序列進(jìn)行按位異或運(yùn)算得到密文序列，因此，流密碼的安全性完全基于密鑰序列的密碼學(xué)指標(biāo)。線性復(fù)雜度是偽隨機(jī)序列的一個很重要的密碼學(xué)指標(biāo)，其刻畫使用線性移位寄存器生成該序列所需線性移位寄存器的最小階。線性復(fù)雜度[1]的計算方法介紹如下。

設(shè)有限域Fq={0,1,2,…,q-1}，q為素數(shù)。設(shè)(un)n≥0=(u0,u1,…,uT-1,…)為Fq上最小周期為T的q元序列（下文中所指的周期均為最小正周期），其線性復(fù)雜度為(un)n≥0，滿足Fq上的如下線性遞歸關(guān)系的最小階，即

其中，i≥0，c0≠0，c1,…,cL-1∈Fq。把最小階對應(yīng)的多項(xiàng)式

稱為序列(un)n≥0的極小多項(xiàng)式。記(un)n≥0的生成多項(xiàng)式為

則(un)n≥0在Fq上的線性復(fù)雜度可通過式(1)[2]計算得到。

即(un)n≥0的線性復(fù)雜度恰好為(un)n≥0的極小多項(xiàng)式的次數(shù)。

但是，一個線性復(fù)雜度高的序列未必具有好的穩(wěn)定性，比如周期為T的二元序列000…0001，其線性復(fù)雜度為T-1，但是當(dāng)該序列改變一位之后即為全0序列，其線性復(fù)雜度降為0。為此，Stamp等[3]引入了k-錯線性復(fù)雜度的概念來衡量序列的穩(wěn)定性，即當(dāng)序列在至多改變k位之后其線性復(fù)雜度的最小值。k-錯線性復(fù)雜度是在重量復(fù)雜度[4]的基礎(chǔ)上給出的，或更早之前Ding等[5]也稱之為球體復(fù)雜度。因此，在密碼學(xué)應(yīng)用中，序列的線性復(fù)雜度不僅要大，而且在序列改變?nèi)舾晌恢笃渚€性復(fù)雜度不應(yīng)顯著降低，即穩(wěn)定性要好[5-6]。

在計算序列的線性復(fù)雜度的算法研究方面，Berlekamp[7]和Massey[8]分別設(shè)計了計算周期序列或有限序列線性復(fù)雜度的算法，即廣為人知的BM（Berlekamp-Massey）算法。之后，Games等[9]給出了一個計算周期為2n的二元序列線性復(fù)雜度的快速算法即Games-Chan算法，該算法的時間復(fù)雜度比BM算法小很多。1993年，Stamp等[3]在Games-Chan算法的基礎(chǔ)上，通過引入一維代價數(shù)組，給出了計算周期為2n的二元序列k-錯線性復(fù)雜度的快速算法。Meidl[10]進(jìn)一步討論了周期為2n的二元序列的穩(wěn)定性。

對于周期為pn的二元序列（p為奇素數(shù)），1999年，魏仕民等[11]擴(kuò)展了Games-Chan算法，提出了一個計算周期為pn的二元序列的線性復(fù)雜度的快速算法。該算法是一個迭代計算的方法，其思想如下。把周期為pn的二元序列(s)按照行為主序排列為一個p×pn-1矩陣，若該矩陣的每一行都相同，則記λ=1，否則λ=0。然后把每一行相加得到一個周期為pn-1的新序列(s')，得到這2個序列線性復(fù)雜度的一個關(guān)系式：LC(s)=LC(s')+λ(p-1)pn-1。以此類推，最后求出二元序列(s)的線性復(fù)雜度。2001年，王磊等[12]基于Stamp-Martin算法[10]的思想，對文獻(xiàn)[11]的算法進(jìn)行了擴(kuò)展，給出了一個計算周期為pn的二元序列的k-錯線性復(fù)雜度的效率更高的算法。需要說明的是，在文獻(xiàn)[11-12]中都要求2為模pn的本原元。最近，陳智雄等[13]給出了一個計算周期為p2的二元序列的k-錯線性復(fù)雜度的快速算法，該算法也把序列排列成p×p矩陣，但是只需計算該矩陣每一列所含非零元素的個數(shù)即可確定周期為p2的二元序列的k-錯線性復(fù)雜度，其中同樣要求2為模p2的本原元。

對于周期為pn的q元序列（p為奇素數(shù)），Xiao等[14]給出計算這類序列在有限域Fq上的線性復(fù)雜度。魏仕民等[15]在文獻(xiàn)[14]的基礎(chǔ)上給出一個確定周期為pn的q元序列的k-錯線性復(fù)雜度的快速算法。白恩健等[16]在文獻(xiàn)[14-15]的基礎(chǔ)上進(jìn)一步給出計算這類序列k-錯線性復(fù)雜度曲線的一個快速算法。蘇明等[17]給出周期為pn的q元序列l(wèi)–錯線性復(fù)雜度期望更緊的上界。在這些文獻(xiàn)中都要求q為模p2的本原元。然而，在文獻(xiàn)[14-16]的算法中都是利用迭代計算的方法得到序列的k-錯線性復(fù)雜度，計算方式相對復(fù)雜，而且隨著序列周期的增大，所需迭代的次數(shù)相應(yīng)增加，導(dǎo)致效率較低。為此，本文考慮計算周期為p2的q元序列的k-錯線性復(fù)雜度的新的快速計算方法，其中p,q為奇素數(shù)且q為模p2的本原元。在該方法中，首先把周期為p2的q元序列以行為主序排列為p×p矩陣。與文獻(xiàn)[14-15]的迭代算法不同，本文方法只需統(tǒng)計各列中元素出現(xiàn)的次數(shù)即可快速確定該序列的k-錯線性復(fù)雜度。

2 序列的k–錯線性復(fù)雜的一般結(jié)果

設(shè)有限域Fq={0,1,2,…,q-1}，其中q為素數(shù)。?=(tn)n≥0是最小周期為p2的q元序列，不妨把其第一周期元素排列成如下矩陣形式。其中，κ1,κ2,κ3如上所述。

證明由k–錯線性復(fù)雜度的定義，不妨設(shè)εk是Fq上最小周期為p2的q元錯誤序列且一個周期中僅含有k個非0元素，則序列?在一個周期內(nèi)改變k個比特后得到新序列記為?k，可表示為?k=?+εk(modq)，即序列?和錯誤序列εk的對應(yīng)比特做模q加法運(yùn)算。用?k(X)和εk(X)分別表示新序列?k和錯誤序列εk的生成多項(xiàng)式。為了討論序列?=(tn)n≥0的k–錯線性復(fù)雜度，只需討論gcd(Xp2-1,?k(X))的不同情況。由于?(X)=，下面根據(jù)序列的復(fù)雜度的4種可能取值分別進(jìn)行討論。

1)當(dāng)LC(?)=p2，由定理1知。下面分情況討論。

② 由引理1的1)知，為使Φ1(X)|?k(X)，則只需改變序列?中若干項(xiàng)后使新序列?k（不妨記為?k=對應(yīng)矩陣排列M(?k)每一列的元素之和相等。首先計算M()?中各列元素之和的結(jié)果，由于重復(fù)出現(xiàn)的次數(shù)則為了使改變后的矩陣的各列元素之和相同，只需改變p-κ1列，而每一列只需改變一個元素即可。即當(dāng)k≥p-κ1，此時可保證Φ1(X)|?k(X)。

③由引理1的2)知，為使Xp-1|?k(X)，則需要通過改變序列?的若干項(xiàng)之后使新序列?k（不妨記為）對應(yīng)矩陣排列M(?k)每一列的元素之和為0。由于為M(?)中各列元素之和為0的個數(shù)，即M(?)中只有p-κ2列的對應(yīng)的列元素之和不等于0。注意到，每一列只需要至多改變一個元素的值即可使這一列的各元素之和為0，那么只需改變M(?)中的p-κ2個元素即可使M(?K)中的各列元素之和均為0。因此，當(dāng)k≥p-κ2時，可保證Xp-1|?k(X)。

④ 由引理1的3)知，為使Φ2(X)|?k(X)，則只需改變M(?)每一列中最少的元素，使同一列中各元素（即tj,tj+p,…,tj+(p-1)p）的取值相同，則第j列最少需要改變p-ω(j)項(xiàng)，j=0,1,…,p-1。那么需要改變的最少項(xiàng)數(shù)為，即k≥κ3，可保證Φ2(X)|?k(X)，此時?k的最小周期至多為p，則LCk(?)≤p。

因此，當(dāng)1≤k

同理討論可得2)～4)中的結(jié)論。

證畢。

3 2類特殊q元序列的k–錯線性復(fù)雜度

3.1 周期為p2的q元Fermat商序列

設(shè)奇素數(shù)p，對于任意與p互素的整數(shù)u，根據(jù)Fermat定理，模p的Fermat商Qp(u)定義為[19]

特別地，當(dāng)p|u時，定義Qp(u)=0。

由Fermat商Qp(u)的定義容易得到引理2。

引理2[19]對任意的u,v∈，有

1)Qp(uv)≡Qp(u)+Qp(v)(modp)

2)Qp(u+kp)≡Qp(u)-ku-1(modp)其中，k∈Z。

相關(guān)文獻(xiàn)表明，由Fermat商定義的序列具有良好的偽隨機(jī)特性[20-22]。杜小妮等[23]利用Fermat商定義了Fq上的q元Fermat序列(fn)n≥0為

其中，q為奇素數(shù)，且為了構(gòu)造平衡序列要求q|(p-1)且。接下來，本文討論該序列的k–錯線性復(fù)雜度。

由引理2的2)知，由式(8)定義的q元Fermat商序列的最小周期為p2。

引理3若，則有{Qp(u+kp)(modp)|k=0,1,2,…,p-1}=Zp。

證明設(shè)k1,k2∈Zp，若Qp(u+k1p)≡Qp(u+k2p)(modp)，由引理2的2)知Qp(u)-k1u-1≡Qp(u)-k2u-1(modp)。又，則k1≡k2(modp)。因?yàn)閗1,k2∈Zp，所以k1=k2。

證畢。

定理3設(shè)p,q為奇素數(shù)且q|(p-1)，q為模p2的本原元，則由式(8)定義的周期為p2的q元Fermat序列(fn)n≥0的k–錯線性復(fù)雜為

證明把周期為p2的q元Fermat序列(fn)n≥0按照式(2)的矩陣形式進(jìn)行排列，即

由引理4和引理1的2)知，(fn)n≥0的線性復(fù)雜度為p2-p且κ1=κ2=p。由引理3及式(8)知，。則由定理2的4)即證。

證畢。

例1設(shè)p=7，q=3，注意到3為模49的本原元，則由式(8)定義的有限域F3上的三元Fermat序列(fn)n≥0的第一個周期為00212002200100201001011221101001020010022002 12000，把該序列排成如下7階方陣

注意到，矩陣的各列元素在有限域F3上之和為0，則κ1=7，κ2=7，κ3=24，且LCk(fn)=其結(jié)果與定理3完全一致。

3.2 周期為p2的q元廣義割圓序列

設(shè)p為奇素數(shù)，整數(shù)模p2的剩余類集為，g為模p2的本原元，則。記為g模p2的乘法階，即

定理4設(shè)p,q為奇素數(shù)且q|(p-1)，q為模p2的本原元，則由式(9)定義的周期為p2的q元廣義割圓序列(sn)n≥0的k–錯線性復(fù)雜為

證明首先把周期為p2的q元廣義割圓序列(sn)n≥0排列成如式(2)所示的矩陣形式，即

由引理7及式(9)知，對于每個1≤j≤p-1，均有sj=sj+?p，其中?=0,1,…,p-1。再由引理6及的定義知，對于1≤j≤p-1中，恰有個sj=i，其中i=0,1,…,q-1。因此，由引理1和定理1知，(sn)n≥0的線性復(fù)雜度為p2-1。而對于j=0，由式(9)知s0=0，{sp,s2p,…,s(p-1)p}中也恰有個i，其中i=0,1,2,…,q-1，則

由q為奇素數(shù)且q|p-1知

證畢。

例2設(shè)p=7，q=3，注意到3為模49的本原元，則由式(9)定義的周期為49的三元序列(sn)n≥0的第一周期為00211200021120202 11201021120 102112020211200021120，同樣把該序列排成如下7階方陣

由上述矩陣知κ1=3，κ2=3，κ3=4且，其結(jié)果與定理4完全一致。

4 效率比較

首先，本文利用式(8)產(chǎn)生3個周期分別為p2=49、361、961的三元Fermat商序列。然后通過編寫Visual C++程序?qū)崿F(xiàn)本文算法與文獻(xiàn)[15]中的算法。對上述3個不同周期的三元Fermat商序列分別運(yùn)行2個程序求出所有可能的k值對應(yīng)的k-錯線性復(fù)雜度，并得到相應(yīng)的運(yùn)行時間。此外，從運(yùn)行結(jié)果上看，2個算法的運(yùn)行結(jié)果完全一致。

運(yùn)行程序的計算機(jī)配置：計算機(jī)型號為HP ProBook 440G2，Windows 7 64位操作系統(tǒng)，4 GB內(nèi)存，Intel(R)Core(TM)i5-4210U CPU@1.70GHz 2.40 GHz處理器。由于每次運(yùn)行所得到的運(yùn)行時間略有不同，因此本文對上述3個不同周期的序列實(shí)例分別連續(xù)運(yùn)行2個程序50次，得到相應(yīng)的運(yùn)行時間并取平均值，具體數(shù)值如表1所示。

表1 2個算法的平均運(yùn)行時間

實(shí)驗(yàn)數(shù)據(jù)如圖1所示。其中，橫坐標(biāo)表示算法輸入的實(shí)例序列對應(yīng)的最小正周期，縱坐標(biāo)表示運(yùn)行時間，豎線顯示實(shí)驗(yàn)數(shù)據(jù)的最大值、最小值和均值。

圖1 2個算法的效率比較

從圖1可知，在求周期為p2的q元序列的k–錯線性復(fù)雜度中，本文算法比文獻(xiàn)[15]算法具有明顯的優(yōu)勢，隨著輸入實(shí)例序列周期的增大，2個算法的效率之差也增大，而且本文算法的運(yùn)行時間隨輸入序列周期的增大變化較小，相對平穩(wěn)。

5 結(jié)束語

本文給出了一個計算周期為p2的q元序列的k-錯線性復(fù)雜度的新算法，其中p,q為奇素數(shù)，且q為模p2的本原元。通過把序列排列成p×p矩陣，然后根據(jù)矩陣各列中元素的分布特點(diǎn)即可得到相關(guān)結(jié)論，而不需要使用文獻(xiàn)[14-15]等算法進(jìn)行迭代計算。由于文獻(xiàn)[14]只是用于求q元序列的線性復(fù)雜度而非用于求k-錯線性復(fù)雜度，本文把3個周期為素數(shù)平方的三元Fermat商序列作為輸入實(shí)例分別運(yùn)行本文算法和文獻(xiàn)[15]的算法，求得所有可能的k值對應(yīng)的k-錯線性復(fù)雜度及所花費(fèi)的運(yùn)行時間，結(jié)果表明2個算法的運(yùn)行結(jié)果完全一致，并且本文算法的效率明顯更高。另外，從本文的分析過程可知，在設(shè)計周期為p2的q元序列時，應(yīng)注意該序列在排列成p×p矩陣時各列元素的分布情況，進(jìn)而構(gòu)造出穩(wěn)定性好的偽隨機(jī)序列。