尋找Span n序列的方法的改進(jìn)

屈　哲　陳克非

1(上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系　上海 200240)2(杭州師范大學(xué)理學(xué)院　浙江 杭州 310036)3(保密通信重點(diǎn)實(shí)驗(yàn)室　四川 成都 610041)

?

尋找Span n序列的方法的改進(jìn)

屈哲1,3陳克非2,3

1(上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系上海 200240)2(杭州師范大學(xué)理學(xué)院浙江 杭州 310036)3(保密通信重點(diǎn)實(shí)驗(yàn)室四川 成都 610041)

de Bruijn序列是一個(gè)周期為2n的0、1序列，去掉n階de Bruijn序列中連續(xù)的n個(gè)0中的一個(gè)得到一個(gè)周期為2n-1的序列，稱為span n序列。一個(gè)n階de Bruijn序列的線性復(fù)雜度在2n-1+n和2n-1之間，然而對應(yīng)的span n序列的線性復(fù)雜度可能降為n。所以span n序列的線性復(fù)雜度成為了衡量一個(gè)de Bruijn序列好壞的重要標(biāo)準(zhǔn)，因此研究生成高線性復(fù)雜度的span n序列的方法是非常有意義的。研究文獻(xiàn)[6]中提出的基于特殊函數(shù)和非線性反饋移位寄存器尋找span n序列的方法，發(fā)現(xiàn)span n序列與參數(shù)t的無關(guān)性，并基于此提出了幾種改進(jìn)算法。對各種算法進(jìn)行橫向比較，并指出了每種算法的局限和優(yōu)點(diǎn)，以及今后可能的改進(jìn)。

非線性反饋移位寄存器de Bruijn序列span n序列

0　引　言

近些年，在偽隨機(jī)序列生成器。流密碼和一些輕量級的分組密碼等領(lǐng)域，非線性反饋移位寄存器NLFSR(Nonlinear Feedback Shift Register)受到了越來越多的關(guān)注?；诜蔷€性反饋移位寄存器的密碼在一些需要高效硬件實(shí)現(xiàn)和高吞吐量等受限制的環(huán)境下表現(xiàn)出良好的實(shí)用價(jià)值，發(fā)揮著重要的作用。

在流密碼中，加密使用的是將明文和密鑰流以比特為單位進(jìn)行那個(gè)異或操作來產(chǎn)生密文。流密碼要求密鑰流是一個(gè)隨機(jī)的比特流，而NLFSR恰好滿足此要求。最大周期NLFSR序列擁有周期長，平衡性好，游程分布均勻，良好的二階自相關(guān)性，低互相關(guān)性，高線性復(fù)雜度等密碼學(xué)性質(zhì)。在eSTREAM[1]流密碼項(xiàng)目中有如Grain和Trivium基于NLFSR的密碼設(shè)計(jì)。

雖然NLFSR擁有如此好的隨機(jī)特性，但是一般給定NLFSR，目前并不存在一個(gè)通用的方法來計(jì)算該NLFSR周期和其他相關(guān)的序列特征。生成指定階數(shù)的最大周期NLFSR序列目前也是一個(gè)開放的問題。目前使用暴力枚舉的方法，可以生成一系列n<25的最大周期NLFSR序列[2]，結(jié)合特殊制作的硬件可以生成n=25和n=27的最大周期NLFSR序列[3]。

本文研究了Kalikinkar Mandal在2012年提出的一種基于WG函數(shù)的搜索span n序列的方法[6]，對該方法做了幾種不同方面的改進(jìn)，并對原方法及改進(jìn)方法做了數(shù)據(jù)分析和比較。

1　反饋移位寄存器和尋找span n序列的方法

本節(jié)將介紹反饋移位寄存器的一些基礎(chǔ)知識，并且研究基于非線性反饋移位寄存器和WG函數(shù)的尋找span n序列的方法。

1.1非線性反饋移位寄存器

移位寄存器是一種以時(shí)間脈沖為觸發(fā)條件的控件，每經(jīng)過一個(gè)脈沖，該器件移動一個(gè)比特并且在輸出端輸出。反饋移位寄存器簡稱FSR(Feedback Shift Register)是指將前一狀態(tài)的輸出再次用作輸入的一種移位寄存器。如果輸出為輸入寄存器的線性函數(shù)，那么叫作線性反饋移位寄存器簡稱LFSR(Linear Feedback Shift Register)，如果是輸入寄存器的非線性函數(shù)，那么叫做非線性反饋以為寄存器簡稱NLFSR(Nonlinear Feedback Shift Register)。

通常FSR可以用反饋函數(shù)來表示：

xi=f(xi-1,xi-2,…,xi-n)

一般的FSR結(jié)構(gòu)如圖1所示。

圖1　FSR結(jié)構(gòu)示意圖

此處，n表示寄存器個(gè)數(shù)，xi表示第i個(gè)脈沖時(shí)的輸出狀態(tài)，f為反饋函數(shù)。其中線性和非線性是反饋函數(shù)f的特征。xi通常取值為0或1，所有的運(yùn)算均在模2的意義下進(jìn)行，即在有限域F2中。所以通常的加法變?yōu)?+0=0，0+1=1+0=1，1+1=0，與計(jì)算機(jī)理論中的異或運(yùn)算結(jié)果相同。在后面的文章中，反饋函數(shù)里的“+”均表示計(jì)算機(jī)里的“異或”。

一個(gè)典型的LFSR方程為：xi=xi-1+xi-3

由反饋函數(shù)知相鄰的三個(gè)比特唯一決定了下一個(gè)比特，與之前的狀態(tài)無關(guān)，如果將(xi-2,xi-1,xi)作為狀態(tài)，狀態(tài)轉(zhuǎn)移的關(guān)系如表1所示。

表1　LFSR狀態(tài)轉(zhuǎn)移

一個(gè)典型的NLFSR方程為：xi=1+xi-3+xi-1+xi-1xi-2

其中常數(shù)項(xiàng)1和二階項(xiàng)xi-1xi-2均為非線性項(xiàng)。狀態(tài)轉(zhuǎn)移表如表2所示。

表2　NLFSR狀態(tài)轉(zhuǎn)移

FSR經(jīng)過足夠多的時(shí)間脈沖可以得到一個(gè)足夠長的序列，序列中連續(xù)的n位也產(chǎn)生了足夠多的n元組狀態(tài)，因?yàn)閚元組最多只有2n個(gè)，所以該序列最終會不斷地重復(fù)一個(gè)片段。重復(fù)片段的最小長度叫做這個(gè)序列的周期，也為該FSR的周期。所以一個(gè)FSR的最大周期為2n，對于LFSR，因?yàn)閒(0,…,0)=0，所以最大周期為2n-1，稱作m序列。對于NLFSR，2n是可以取到的，稱作M序列，也叫作de Bruijn序列。

LFSR背后的數(shù)學(xué)理論已經(jīng)研究得非常清楚，可以根據(jù)階數(shù)構(gòu)造出m序列LFSR。NLFSR的理論目前并不明確，給定反饋函數(shù)現(xiàn)在并沒有有效的算法確定其周期，給定階數(shù)n，現(xiàn)在也沒有有效的算法構(gòu)造出最大周期序列。關(guān)于NLFSR，目前的問題還都非常開放，還有很多值得研究和挖掘的東西。

在FSR中，如果將每一個(gè)n元組狀態(tài)看作一個(gè)點(diǎn)，能夠轉(zhuǎn)移的狀態(tài)之間連邊，那么每一個(gè)狀態(tài)有兩條入邊，兩條出邊，按照這種方式構(gòu)成的圖稱作de Bruijn圖。圖上的任意一條路徑都形成了一個(gè)二元序列，其中Hamiltonian路徑長度最長，為2n，形成的序列稱為de Bruijn序列，即每一個(gè)n元組均出現(xiàn)一次的序列。將de Bruijn序列中連續(xù)的n個(gè)0中的一個(gè)去掉得到的序列叫做modified de Bruijn序列，也稱作span n序列。m序列即為span n序列的一個(gè)子集。span n序列具有非常好的密碼學(xué)性質(zhì)，但是目前并沒有通用生成span n序列的方法。本文將在第2節(jié)研究一些尋找span n序列的方法。

衡量一個(gè)序列性質(zhì)好壞的一個(gè)重要指標(biāo)為線性復(fù)雜度，即可以生成該序列的所有LFSR中階數(shù)最小的那一個(gè)的數(shù)值。已知序列可以使用Berlekamp-Massey算法計(jì)算其線性復(fù)雜度。

1.2基于特殊函數(shù)尋找span n序列的方法

Kalikinkar Mandal在2012年提出了一種基于WG函數(shù)的搜索span n序列的方法[6]。

Welch-Gong(WG)變換序列是周期為2n-1的具有二階自相關(guān)性的二元序列。Golomb，Gong和Gaal在1998年發(fā)現(xiàn)WG變換序列并且驗(yàn)證了5≤n≤20的情況[7]。不久之后，No等人發(fā)現(xiàn)了另外一個(gè)構(gòu)造WG序列的方法，并且驗(yàn)證了5≤n≤23的情況[8]。Dillon在1998年首次證明了n為奇數(shù)的情況[9]，Dobbertin和Dillon在1999年又證明了n為偶數(shù)的情況[10]，使得整個(gè)結(jié)果完整。

設(shè)n不被3整除，那么階數(shù)為n的WG變換函數(shù)為：

如果n=3k-1，記：

q1=2k+1

q2=22k-1+2k-1+1

q3=22k-1-2k-1+1

q4=22k-1+1

如果n=3k-2，記：

q1=2k-1+1

q2=22k-2+2k-1+1

q3=22k-2-2k-1+1

q4=22k-1-2k-1+1

那么WG變換函數(shù)為：

WGP(x)=h(x+1)+1

其中：

h(x)=x+xq1+xq2+xq3+xq4

定義：

fd(x)=Tr(h(xd))d∈Dt

其中：

Tr(x)=x+x2+…+x2n-1

Dt={d|gcd(d,2n-1)=1}模2n-1的2-分圓陪集首

記Fn表示n階有限域，那么h(x)為從F2n到F2n的函數(shù)，Tr(x)為從F2n到F2的函數(shù)，所以fd(x)為從F2n到F2的函數(shù)。利用fd(x)有如下構(gòu)造NLFSR的方法。

對于n階NLFSR，記寄存器編號為0，1，…，n-1，選擇寄存器t元組(r1,r2,…,rt)滿足0

xn+k=xk+fd(Rk)Rk=(xr1+k,xr2+k,…,xrt+k)

NLFSR構(gòu)造如圖2所示。

圖2　使用WG函數(shù)構(gòu)造的NLFSR結(jié)構(gòu)圖

按照這種方法構(gòu)造的NLFSR由以下五個(gè)參數(shù)組成：

n—— 寄存器個(gè)數(shù)

d—— 決定數(shù)

t——在n-1個(gè)寄存器中選擇t個(gè)

t-tap——(r1,r2,…,rt)，具體選擇了哪t個(gè)

pp——本原多項(xiàng)式，決定了反饋函數(shù)運(yùn)算的有限域

固定n和t，暴力枚舉剩余的參數(shù)d，t-tap，pp得到一個(gè)NLFSR后，然后驗(yàn)證其周期，如果為2n-1，那么便找到了一個(gè)span n序列。

(1)

2　尋找span n序列的幾種算法

本文提出了幾種基于文獻(xiàn)[6]的尋找NLFSR的方法。基本算法為枚舉+驗(yàn)證，我們每次根據(jù)枚舉算法找到一個(gè)參數(shù)組(t-tap,d,pp)，然后驗(yàn)證該NLFSR產(chǎn)生的序列是否為我們所需要的span n序列。在驗(yàn)證部分，目前并沒有有效的算法，本文采取使用按照NLFSR規(guī)則生成序列并驗(yàn)證的方法。所以我們的改進(jìn)著眼于枚舉部分，通過減小搜索空間來提高搜索效率。

2.1樸素暴力搜索

這是文獻(xiàn)[6]所提出的算法，也是本文所研究和需要改進(jìn)的算法。記為去掉使得為線性函數(shù)的元素的集合。

算法1樸素暴力搜索

輸入：寄存器個(gè)數(shù)n，選擇出的寄存器個(gè)數(shù)t(t

輸出：所有生成span n序列的NLFSR，以參數(shù)組(t-tap,d,pp)給出。

算法：

(1) 枚舉度為t的本原多項(xiàng)式pp，確定運(yùn)算的有限域F2t；

(3) 枚舉t-tap，除去0號寄存器，在1到n-1號寄存器中選擇t個(gè)；

(4) 驗(yàn)證(t-tap, d, pp)對應(yīng)的NLFSR的周期，若為2n-1，則輸出該NLFSR。

空間復(fù)雜度：因?yàn)镹LFSR最大周期為2n-1，所以空間復(fù)雜度為O(2n)。

該算法的缺點(diǎn)是在t=4時(shí)找到的span n序列線性復(fù)雜度過小，文獻(xiàn)[6]中也沒有討論t=4的情況。在n較大時(shí)，隨著t的增加，搜索空間急劇增大，不利于span n序列的查找。

2.2基于GPU并行搜索

使用NVIDIA提出的CUDA[11]并行搜索。給定(n,t)，通過將參數(shù)組(t-tap,d,pp)分配到不同的線程塊上，來加速枚舉過程。

算法2基于GPU并行搜索

輸入：寄存器個(gè)數(shù)n，選擇出的寄存器個(gè)數(shù)t(t

輸出：所有生成span n序列的NLFSR，以參數(shù)組(t-tap, d, pp)給出。

算法：

(1) 確定線程塊各個(gè)維度大小，在每一個(gè)線程塊中均執(zhí)行(2)、(3)、(4)、(5)；

(2) 枚舉度為t的本原多項(xiàng)式pp，確定運(yùn)算的有限域F2t；

(4) 枚舉t-tap，除去0號寄存器，在1到n-1號寄存器中選擇t個(gè)；

(5) 驗(yàn)證(t-tap,d,pp)對應(yīng)的NLFSR的周期，若為2n-1，則輸出該NLFSR。

在CUDA并行編程框架里，線程塊是三維的，所以可以將t-tap,d,pp三個(gè)參數(shù)剛好分配到不同的維度上。

空間復(fù)雜度：，記線程塊個(gè)數(shù)為N，則空間復(fù)雜度為N×O(2n)=O(N·2n)。

并行是加速枚舉過程的一個(gè)有效辦法，但缺點(diǎn)是對于空間消耗過大，對于單臺機(jī)器很快就會超過機(jī)器空間限制?？赡艿母倪M(jìn)方法是將不同的參數(shù)(t-tap,d,pp)分配到不同的機(jī)器上，因?yàn)閱栴}的特殊性，可以舍棄一些并行框架的限制，采取“分開即并行”的策略。

2.3對搜索空間大小設(shè)定閾值搜索

通過式(1)可以根據(jù)(n,t)計(jì)算出所需的計(jì)算量，所以我們可以預(yù)先指定一個(gè)閾值L，只有當(dāng)計(jì)算量不大于L時(shí)我們才進(jìn)行搜索，否則跳過。這樣對于特定的n我們有選擇地去找t來進(jìn)行后續(xù)的搜索。

算法3對搜索空間大小設(shè)定閾值搜索

輸入：寄存器個(gè)數(shù)n。

輸出：給出部分生成span n序列的NLFSR，以參數(shù)組(t,t-tap, d, pp)給出。

算法：

(1) 設(shè)定閾值L；

(2) 枚舉t;

(3) 由n，t計(jì)算Spacen,t，若Spacen,t

(4) 枚舉度為t的本原多項(xiàng)式pp，確定運(yùn)算的有限域F2t；

(6) 枚舉t-tap，除去0號寄存器，在1到n-1號寄存器中選擇t個(gè)；

(7) 驗(yàn)證(t-tap,d,pp)對應(yīng)的NLFSR的周期，若為2n-1，則輸出該NLFSR。

空間復(fù)雜度：O(2n)。

時(shí)間復(fù)雜度：因?yàn)橹挥挟?dāng)搜索空間小于L時(shí)才進(jìn)行搜索，所以時(shí)間復(fù)雜度為O(nL)。

如果閾值L設(shè)定的過小的話，當(dāng)n比較大時(shí)，t最多只能取到4，而這種情況搜索出的span n序列的線性復(fù)雜度偏低。

2.4針對t=4的情況擴(kuò)大搜索空間尋找高線性復(fù)雜度span n序列

由式(1)可知，t越小枚舉量越小，文獻(xiàn)[6]里t的最小值取為5。我們?nèi)=4運(yùn)行算法2.1，發(fā)現(xiàn)在搜索量更小的情況下反而找到了更多的span n序列，但是找出來的序列線性復(fù)雜度都不高，在2n附近。

為了提高所找到span n序列的線性復(fù)雜度，我們在選出t-tap后對這些寄存器按照事先的約定做一個(gè)置換，然后再運(yùn)行后面的算法。這樣搜索空間的大小變?yōu)橹暗膖!=4!=24倍，但是找到了高線性復(fù)雜度的span n序列，集中在2n-1。

算法4針對t=4的情況擴(kuò)大搜索空間尋找高線性復(fù)雜度span n序列

輸入：寄存器個(gè)數(shù)n。

輸出：給出部分生成span n序列的NLFSR，以參數(shù)組(p4,d,pp)給出。

算法：

(1) 枚舉度為t=4的本原多項(xiàng)式pp，確定運(yùn)算的有限域F2t；

(3) 枚舉四元組p4=(r1,r2,r3,r4)，其中ri互不相同，0

(4) 驗(yàn)證(p4,d,pp)所構(gòu)成的NLFSR的周期，如果為span n序列，那么輸出(4,d,pp)；

p4的作用相當(dāng)于在2.1節(jié)中的t-tap選擇出來后加入了一個(gè)排列，將t元向量中元素的位置改變。

空間復(fù)雜度：O(2n)。

該算法優(yōu)點(diǎn)是時(shí)間復(fù)雜度小，并且可以找到高線性復(fù)雜度span n序列。缺點(diǎn)為當(dāng)n增大后span n序列越來越少。

2.5對部分寄存器添加置換操作，進(jìn)行a+b搜索

將2.1節(jié)和2.4節(jié)結(jié)合起來形成a+b搜索算法。t不變，隨著n的增大，搜索效率降低，我們可以通過增加排列的方法來增大搜索空間提高找到的span n序列數(shù)量。然而通過增加排列所得到的搜索空間是之前的t!倍，這個(gè)當(dāng)t增大時(shí)并不利于搜索，我們可以采取固定t中的b個(gè)，而對剩余的a=t-b個(gè)做排列，這樣仍然可以大幅度提高找到的span n序列的數(shù)量。

算法5對部分寄存器添加置換操作，進(jìn)行a+b搜索

輸入：寄存器個(gè)數(shù)n，參與排列的寄存器個(gè)數(shù)a，不動的寄存器個(gè)數(shù)b(t=a+b)。

輸出：給出部分生成span n序列的NLFSR，以參數(shù)組(pa,pb,d,pp)給出。

算法：

(1) 枚舉度為t的本原多項(xiàng)式pp，確定運(yùn)算的有限域F2t；

(3) 枚舉參與置換的寄存器a元組pa；

(4) 枚舉不參與置換的寄存器b元組pb；

(5) 驗(yàn)證(pa,pb,d,pp)所構(gòu)成的NLFSR的周期，如果為span n序列，那么輸出(4,d,pp)；

空間復(fù)雜度：O(2n)。

該算法可以彌補(bǔ)算法2.1節(jié)和算法2.4節(jié)的不足，在維持t=a+b較小的情況下，保證搜索空間不會過大，然后通過對a個(gè)寄存器做置換操作，來增加span n序列的數(shù)量。

2.6隨機(jī)枚舉參數(shù)進(jìn)行搜索

采用隨機(jī)化的方法來枚舉參數(shù)，然后驗(yàn)證。將問題轉(zhuǎn)化為給定n，找到一個(gè)n階span n序列，不同于之前遍歷整個(gè)搜索空間找到所有span n序列的算法。

算法6隨機(jī)枚舉參數(shù)進(jìn)行搜索

輸入：寄存器個(gè)數(shù)n。

輸出：給出部分生成span n序列的NLFSR，以參數(shù)組(t-tap,d,pp)給出。

算法：

(1) 隨機(jī)選組參數(shù)(t-tap, d, pp)；

(2) 驗(yàn)證(t-tap,d,pp)對應(yīng)的NLFSR的周期，若為2n-1，則輸出該NLFSR。

空間復(fù)雜度：O(2n)。

該算法不再拘泥于某個(gè)t，然后針對(n,t)進(jìn)行搜索，而是在整個(gè)搜索空間中進(jìn)行隨機(jī)化枚舉，有效避免了搜索了整個(gè)(n,t)空間，卻沒有找到任何一個(gè)span n序列的情況，大大提高枚舉的效率。

3　實(shí)驗(yàn)結(jié)果與相關(guān)分析

本節(jié)將列舉一些第2節(jié)提出的幾種算法的一些實(shí)驗(yàn)數(shù)據(jù)并對數(shù)據(jù)進(jìn)行相關(guān)的分析。

3.1樸素暴力算法

本小節(jié)敘述了文獻(xiàn)[6]中算法的一些基本特征。

根據(jù)式(1)，搜索空間分布如表3所示。

表3　(n,t)搜索空間大小

經(jīng)過實(shí)驗(yàn)得到搜索消耗時(shí)間如表4所示，單位為秒。

表4　(n,t)搜索時(shí)間

通過表3和表4可以看到搜索空間和搜索時(shí)間兩者的走向基本一致，這也從另一個(gè)側(cè)面說明了第3節(jié)中用搜索空間來描述時(shí)間復(fù)雜度的合理性。

搜索到span n序列的數(shù)量如表5所示。

表5　參數(shù)(n, t)下span n序列數(shù)量

對于每一個(gè)(n,t)，考察span n序列所占搜索空間的比例，如表6所示。

表6　參數(shù)(n, t)下span n序列數(shù)量占總搜索空間比例

隨著n的增加，span n序列比例減小，然而固定n，對于不同的t，span n序列比例相對穩(wěn)定，這也為算法6提供了一定數(shù)據(jù)上的依靠。

3.2基于GPU并行搜索

并行搜索的瓶頸在于每一個(gè)線程塊都需要O(2n)的空間，這在n比較大時(shí)是無法接受的。對于較小的n，因?yàn)椴⑿械母鞣N協(xié)調(diào)性工作，其搜索效率并不比算法1來得更好。

3.3對搜索空間大小設(shè)定閾值搜索

根據(jù)表6可知，對于相同的n，搜索不同的t搜索效率大致相同，但是不同的t對應(yīng)的搜索空間大小是不同的，這啟發(fā)我們可以預(yù)先按照搜索空間大小排序，然后按照給定的一個(gè)閾值L只對搜索空間小于L的t進(jìn)行搜索。由于搜索效率并未損失而搜索空間由于閾值的限制又相對較小，這使得搜索可以更快的進(jìn)行。

表7為L=1010時(shí)的搜索數(shù)據(jù)。

表7　閾值 搜索到的span n序列數(shù)量

在n較大時(shí)，t非常小，只能取2或4。雖然能夠獲得span n序列，但是序列的線性復(fù)雜度都較低，由Berlekamp-Massey算法計(jì)算得到序列的線性復(fù)雜度在2n附近。

3.4針對t=4的情況擴(kuò)大搜索空間尋找高線性復(fù)雜度span n序列

算法4是對算法3的改進(jìn)。表8為t=4 span n序列所占總搜索空間的比例。

表8　t=4時(shí)span n序列占總搜索空間比例

t=4時(shí)span n序列相比t>4時(shí)有大幅提升，但是序列線性復(fù)雜度過低。我們所做的是在提取出t-tap后再進(jìn)行一個(gè)置換操作，然后運(yùn)行之后的運(yùn)算，最后篩選出線性復(fù)雜度高的span n序列。

表9為添加置換操作后找到的高線性復(fù)雜度span n序列數(shù)量。

表9　添加置換后t=4高線性復(fù)雜度span n序列數(shù)量

經(jīng)過置換后的span n序列復(fù)雜度在2n-1附近，相比于之前的2n有大幅提高。遺憾的是在n=17沒有找到高線性復(fù)雜度span n序列。

3.5對部分寄存器添加置換操作，進(jìn)行a+b搜索

算法5為算法1和算法4的結(jié)合。表10為固定b=1個(gè)寄存器為1號寄存器，剩余a=4個(gè)寄存器做置換的結(jié)果，即4+1的一個(gè)部分結(jié)果，因?yàn)椴⑽磳=1個(gè)寄存器做枚舉。

表10　4+1與傳統(tǒng)t=5時(shí)span n序列數(shù)量對比

雖然并未對b=1個(gè)寄存器做枚舉，但是表10已足夠說明4+1方式可以搜索到更多的span n序列。

3.6隨機(jī)枚舉參數(shù)進(jìn)行搜索

隨機(jī)化搜索基于表6的結(jié)果。因?yàn)椴煌膖所含span n序列比例基本不變，我們可以認(rèn)為span n序列在整個(gè)參數(shù)空間內(nèi)均勻分布，這啟發(fā)我們可以隨機(jī)化參數(shù)然后驗(yàn)證尋找span n序列。問題也變?yōu)榻o定階數(shù)n，尋找一個(gè)span n序列NLFSR。

表11為搜索到的span n序列NLFSR與所耗時(shí)間。

表11　使用隨機(jī)化搜索到一個(gè)span n序列的時(shí)間

算法1是最為樸素的算法，也是其他算法的基礎(chǔ)，缺點(diǎn)是當(dāng)n較大時(shí)，搜索空間太大。通過實(shí)驗(yàn)3.1得到的數(shù)據(jù)可以看到對于不同的t，span n序列的比例是相對穩(wěn)定的，即搜索效率基本不變，基于此發(fā)展出了算法3和算法6。在算法3中我們預(yù)先對不同的t計(jì)算其搜索空間，然后只對小于某閾值L的t進(jìn)行下一步搜索，因?yàn)橹盎谒阉餍什蛔兊陌l(fā)現(xiàn)，這樣的搜索是有效的。span n序列在不同的t上分布相對穩(wěn)定可以認(rèn)為span n序列在參數(shù)(t-tap, pp, d)上分布均勻，因此可以采用隨機(jī)方法來進(jìn)行搜索，實(shí)驗(yàn)3.6的數(shù)據(jù)也證明了這一點(diǎn)，找到了文獻(xiàn)[6]中未涉及的n=21的一組span n序列，這只是在普通PC機(jī)上算出來的結(jié)果，可以認(rèn)為如果使用計(jì)算能力更高的PC機(jī)的話，結(jié)果可能會更好。基于算法3中t=4時(shí)span n序列比例的異常即線性復(fù)雜度過小的事實(shí)，發(fā)展出了算法4。算法4利用t=4時(shí)搜索空間小的優(yōu)勢，添加置換操作，從而在仍然維持小搜索空間的情況下找到了更多的span n序列。在n較大時(shí)，算法4失去了作用，然而和算法1結(jié)合，發(fā)展出了算法5。我們?nèi)匀恍枰S持t較小，使得搜索空間維持在可以計(jì)算的范圍，然后只對部分寄存器做算法4中的置換操作。由實(shí)驗(yàn)3.5的結(jié)果可知算法5相比于算法1在相同的t的情況下，找到了更多的span n序列。

4　結(jié)　語

本文對文獻(xiàn)[6]提出的搜索span n序列的方法做了研究和改進(jìn)。針對t=4時(shí)span n線性復(fù)雜度低的情況添加置換做了改進(jìn)?；诒?的結(jié)果提出了隨機(jī)化搜索的方法，該方法可以對n>20的情況作處理，這點(diǎn)優(yōu)于相比于原始算法并給出了n=21時(shí)的一組數(shù)據(jù)。

關(guān)于算法1肯定還有很多值得探討的問題，關(guān)于NLFSR也還有很多開放的問題值得去探索。

[1] eSTREAM:the ECRYPT Stream Cipher Project[EB/OL].http://www.ecrypt.eu.org/stream/.

[2] Dubrova E.A list of maximum-period NLFSRs[R].Cryptology ePrint Archive,Report 2012/166 (2012).http://eprint.iacr.org/2012/166.

[3] Rachwalik T,Szmidt J,Wicik R,et al.Generation of Nonlinear Feedback Shift Registers with special-purpose hardware[C]//Communications and Information Systems Conference (MCC), 2012 Military,1-4.[4] Chan A H,Games R A,Key E L.On the complexities of de Bruijn sequences[J].Journal of Combinatorial Theory,Series A,1982,33(3):233-246.

[5] Mayhew Gregory L,Solomon W Golomb.Linear spans of modified de Bruijin sequences[J].IEEE transactions on information theory,1990,36(5):1166-1167.

[6] Mandal K,Gong G.Probabilistic Generation of Good Span n Sequences from Nonlinear Feedback Shift Registers[R].CACR Technical Report (2012).

[7] No J S,Golomb S W,Gong G,et al.Binary Pseudorandom Sequences of Period 2n-1 with Ideal Autocorrelation[J].IEEE Transactions on Information Theory,1998,44(2):814-817.

[8] No J S,Chung H,Yun M S.Binary pseudorandom sequences of period 2m-1with ideal autocorrelation generated by the polynomial zd+(z+1)d[J]. InformationTheory, IEEE Transactions on,1998,44(3):1278-1282.

[9] Dillon J F.Multiplicative difference sets via additive characters[J].Designs,Codes and Cryptography,1999,17(1-3):225-235.

[10] Dillon J F,Dobbertin H.New cyclic difference sets with Singer parameters[J].Finite Fields and Their Applications,2004,10(3):342-389.

[11] Nvidia C.What is CUDA[EB/OL].[2013-5-1].http://www.nvidia.com/object/cuda_home_new.html.

IMPROVEMENT IN SEARCHING METHOD OF SPAN N SEQUENCES

Qu Zhe1,3Chen Kefei2,3

1(DepartmentofComputerScienceandEngineering,ShanghaiJiaoTongUniversity,Shanghai200240,China)2(SchoolofScience,HangzhouNormalUniversity,Hangzhou310036,Zhejiang,China)3(ScienceandTechnologyonCommunicationSecurityLaboratory,Chengdu610041,Sichuan,China)

de Bruijn sequence is a binary sequence with length 2n, by removing one zero from consecutive n zero of n-stage de Bruijn sequence, we get a sequence with length 2n-1 which is called span n sequence. The linear complexity of an n-stage de Bruijn sequence is between 2n-1+n and 2n-1, but the linear complexity of corresponding span n sequence could drop to n. Because of this, the linear complexity of span n sequence becomes an important property in measuring the quality of de Bruijn sequence, so it is very meaningful to study how to generate span n sequence with high linear complexity. In this article we study the method of searching span n sequence based on special function and non-linear feedback shift register proposed in literature [6], and find that the independency between span n sequence and parameter t, on this basis we propose some improved methods. We also make the horizontal comparison on various algorithms, and point out their pros and cons and the possible improvement in the future.

Non-linear feedback shift registerde Brujin sequenceSpan n sequence

2015-09-07。屈哲，碩士，主研領(lǐng)域：偽隨機(jī)序列。陳克非，教授。

TP3

A

10.3969/j.issn.1000-386x.2016.10.069