周期為p2的q元序列的k–錯線性復雜度

吳晨煌，許春香，杜小妮

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

1 引言

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

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

其中，i≥0，c0≠0，c1,…,cL-1∈Fq。把最小階對應的多項式

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

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

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

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

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

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

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

2 序列的k–錯線性復雜的一般結果

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

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

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

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

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

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

因此，當1≤k

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

證畢。

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

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

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

特別地，當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。

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

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

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

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

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

證畢。

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

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

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

證畢。

例1設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)=其結果與定理3完全一致。

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

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

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

證明首先把周期為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的線性復雜度為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設p=7，q=3，注意到3為模49的本原元，則由式(9)定義的周期為49的三元序列(sn)n≥0的第一周期為00211200021120202 11201021120 102112020211200021120，同樣把該序列排成如下7階方陣

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

4 效率比較

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

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

表1 2個算法的平均運行時間

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

圖1 2個算法的效率比較

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

5 結束語

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