周建欽，歐陽孔禮

（1.安徽工業(yè)大學計算機學院，安徽馬鞍山 243002；2.杭州電子科技大學通信工程學院，浙江杭州 310018）

GF（q）上pn－周期序列的k錯線性復雜度＊

周建欽1，2，歐陽孔禮1

（1.安徽工業(yè)大學計算機學院，安徽馬鞍山 243002；2.杭州電子科技大學通信工程學院，浙江杭州 310018）

周期序列的錯誤線性復雜度是度量密鑰流穩(wěn)定性的一個重要指標.首先改寫GF（q）上pn周期序列的k錯線性復雜度快速算法，給出其m緊錯線性復雜度的快速算法；然后研究相應k錯線性復雜度的誤差向量，得到計算誤差向量的算法，即在此誤差向量下，可以實現(xiàn)原始序列的k錯線性復雜度.其中p為奇素數(shù)，q是模p2的一個本原根.

k錯線性復雜度；m緊錯線性復雜度；誤差向量

1 相關定義

在流密碼理論研究中，密鑰流序列的線性復雜度是度量其強度的一個重要指標［1－2］.為了抵御Berlekamp-Massey［1－2］算法的攻擊，序列的線性復雜度要盡可能地高.然而在保證序列線性復雜度足夠高的同時，還要要求在改變少量比特的情況下，序列的線性復雜度下降得較小.為此，丁存生等［3］率先給出一些度量序列穩(wěn)定性的指標，隨后國外學者Stamp M等［4］獨立提出了k錯線性復雜度的概念來研究序列的穩(wěn)定性.

定義1［1］周期序列的線性復雜度定義為能夠產(chǎn)生周期序列s的最小線性移位寄存器（LFSR）的階數(shù)，記為c（s）.

定義3［5］序列s的最小錯誤minerror（s）定義為滿足不等式ck（s）＜c（s）的最小正整數(shù).即為使其線性復雜度下降，至少要改變序列s的元素數(shù)目.

綜合上述概念，文獻［6－7］提出了m緊錯線性復雜度的概念來研究周期序列的穩(wěn)定性，并給出了2n周期和pn周期二元序列的m緊錯線性復雜度快速算法.

定義4［6－7］序列s的m緊錯線性復雜度記為（km，cm），其中km表示序列k錯線性復雜度的第m個下降點，cm表示km錯線性復雜度.

若有周期序列s，顯然，當m＝0時，c0即為原序列s的線性復雜度；當m＝1時，k1即為minerror（s），c1為序列s的k1錯線性復雜度.

例如，設序列s是一個周期為81的5元序列，其第一周期s81＝141022134 423301104 001134332 143022134 423301104 001134332 143022134 423301104 001134302，則可以得到序列s的k錯線性復雜度曲線和m緊錯線性復雜度曲線分別如圖1，2所示.

圖1 k錯線性復雜度曲線

圖2 m緊錯線性復雜度曲線

關于求2n周期二元序列k錯線性復雜度的Stamp-Martin算法［4］有一個重要的思想［7］：如果算法中第j次循環(huán)可使線性復雜度降低的值記為dj，那么以后所有循環(huán)可能降低線性復雜度的總和不會大于dj.若一個周期序列k錯線性復雜度的算法與Stamp-Martin算法類似，則稱該算法滿足Stamp-Martin模式.易證明，滿足Stamp-Martin模式的算法也可以類似地拓展為m緊錯線性復雜度算法.對于一些現(xiàn)有的求線性復雜度的快速算法，如GF（2）上2npm周期序列線性復雜度的快速算法［8］，這樣的算法不容易推廣成為求k錯線性復雜度的快速算法.而對于給定的值m，現(xiàn)有的線性復雜度的快速算法一般均可以推廣為求m緊錯線性復雜度的快速算法.m緊錯線性復雜度同時包括多個研究序列強度及穩(wěn)定性的概念（線性復雜度、k錯線性復雜度以及序列最小錯誤minerror（s）等），因此具有重要的研究意義與價值.

文獻［6－7］給出了2n周期和pn周期二元序列的m緊錯線性復雜度快速算法，文獻［9］給出了改寫的Stamp-Martin算法與計算誤差向量的快速算法.筆者通過改寫文獻［10］中GF（q）上pn周期序列的k錯線性復雜度的快速算法，給出了其m緊錯線性復雜度和相應誤差向量的快速算法，并通過實例進行說明其有效性.這里p是奇素數(shù)，q是模p2的一個本原根.

2 改寫的k錯線性復雜度快速算法

文獻［10］給出了確定q元pn周期序列k錯線性復雜度的快速算法，以下稱為魏－董－肖算法.在魏－董－肖算法中，cost只計算了為改變當前序列中的ai而多付出的代價.事實上，可以改變cost的定義為：為改變當前序列中的ai而必須改變原始序列的比特數(shù).這樣即使保持當前元素位置不變時也可能需要付出代價，即此時cost也可能不為0.現(xiàn)首先對魏－董－肖算法進行改寫，改寫后的算法與魏－董－肖算法的時間復雜度相同，但易于理解和推廣.

下面給出改寫的q元pn－周期序列k錯線性復雜度的快速算法.

設s＝（s0，s1，...）為GF（q）上周期N＝pn的序列，其中p是奇素數(shù)，q是模p2的一個本原根，sN＝（s0，s1，...，sN－1）是s的第1個周期，記a＝（a0，a1，...，al－1）.計算s的k錯線性復雜度的算法如下所示.

算法1 初始值a←sN，l←pn，c←0，cost［i，ai］←0，當0≤h≤q－1且h≠ai時，cost［i，h］←1（i＝0，1，...，l－1）.

最終可得周期序列s的k錯線性復雜度ck（s）＝c.

在算法1中，k是一個固定的值，cost［i，h］的定義更合理，使得計算T和新的cost［i，h］變得容易理解.由如下定理1，2和文獻［10］中的相關證明，易知算法1的正確性.

定理1 cost［i，ai］≤cost［i，h］（h＝0，1，...，q－1；i＝0，1，...，l－1；l＝pn，pn－1，...，p，1）.

證明 當l＝pn時，若h＝ai，則cost［i，h］＝0，若h≠ai，則cost［i，h］＝1，成立.若第j步T≤k，則cost［i，ai］＝Ti≤Tih＝cost［i，h］；若第j步T＞k，由cost［i＋jl，ai＋jl］≤cost［i＋jl，ai＋jl＋dj］，則

3 m緊錯線性復雜度的快速算法

對魏－董－肖算法的改寫，沒有影響算法的結構，而修改后的算法更方便推廣為計算m緊錯線性復雜度的快速算法.

在上述算法1的基礎上，通過適當修改，易求GF（q）上pn周期序列的m緊錯線性復雜度.具體修改如下：

（a）在初始值中添加Tmin←pn；

（b）在（ⅳ）最前部添加語句“若T＜Tmin，則Tmin←T”.

（c）在（ⅱ）中c←c＋1之后添加語句“若cost［0，0］＜Tmin，則Tmin←cost［0，0］”.

注 Tmin表示的是使線性復雜度再次下降需要改變原始序列的最小比特數(shù).

作上述修改后得到的算法記為算法2.

在首次調(diào)用算法2時，此時k＝0，本次調(diào)用結束后即可以得到的序列s的線性復雜度c0（此時k＝0，0錯線性復雜度即為原始序列的線性復雜度），除此之外還可以得到使得線性復雜度第1次下降需要改變的比特數(shù)目Tmin；此時令k＝Tmin，再次調(diào)用算法2，記當前k為k1，可以得到序列的k1錯線性復雜度c1和使得線性復雜度再次下降需要改變的比特數(shù)目Tmin；通過反復調(diào)用算法2，即可得到序列s的m緊錯線性復雜度.

例1 設s是GF（5）上的周期為81的序列，其第1個周期s81＝141022134 423301104 001134332 143022134 423301104 001134332 143022134 423301104 001134302，其m緊錯線性復雜度求解過程如下：此時l＝81，11次調(diào)用算法2，依次得到（0，80），（2，26），（3，25），（9，24），（11，21），（14，18），（44，7），（47，6），（50，2），（62，1），（65，0）.由此易得圖2所示序列s的m緊錯線性復雜度曲線.

若按照魏－董－肖算法來計算序列的k錯線性復雜度曲線，先后共需要調(diào)用算法82次，得到圖1所示序列s的k錯線性復雜度曲線，而利用算法2只需要11次.文獻［11］也給出了確定pn－周期的q元序列k錯線性復雜度曲線的算法，但是利用文中的算法更易于理解.另外文獻［11］中部分計算結果是錯誤的：文中c1（s）＝79，c3（s）＝c4（s）＝26，c9（s）＝c10（s）＝c11（s）＝c12（s）＝c13（s）＝25，c14（s）＝c15（s）＝c16（s）＝21.事實上，正確結果為c1（s）＝80，c3（s）＝c4（s）＝25，c9（s）＝c10（s）＝c11（s）＝c12（s）＝c13（s）＝24， c14（s）＝c15（s）＝c16（s）＝18.

由例1可知，周期序列s的線性復雜度、線性復雜度每次下降所需要改變的比特數(shù)以及下降后的值，都可由求解m緊錯線性復雜度的過程計算出來.因此，對于m緊錯線性復雜度的研究具有重要的意義與價值.

4 誤差向量的計算

在k錯線性復雜度的實際應用中，誤差向量的計算是非常重要的.在算法1的基礎上，給出k錯線性復雜度對應的誤差向量.即在此誤差向量下，原始序列可以實現(xiàn)k錯線性復雜度ck（s）.

以下給出計算GF（q）上pn周期序列計算對應誤差向量的有效算法，其中p和q都是奇素數(shù)，并且q是模p2的一個本原根.

（ⅴ）start←start－1，l←1，轉向（ⅵ）.

（ⅵ）若l＜pn－1，則轉向（ⅶ）；否則error＝begin－s（mod q），停止.

最后可同時得到序列s的k錯線性復雜度ck（s）＝c與使得ck（s）＝c（s＋e）成立的誤差向量e＝error.

算法3中，changeto［i，h］存放的是：為得到當前序列中的cost［i，h］，上一步序列中ai，ai＋l，...，ai＋（p－1）l需要改變成的值.算法3最初得到的begin記錄上一步，a，...，a應該變成的值h0，h1，...，hp－1，再根據(jù)changeto［start＋i，hi］得到上一步序列應該變成的值，i＝0，1，...，p－1；以此類推，最后得到原始序列應該變成的新序列，從而推導出誤差向量error.

例2 五元序列的一個周期s81＝141022134 423301104 001134332 143022134 423301104 001134332 143022134 423301104 001134302，求4錯線性復雜度c4（s）及對應的誤差向量.

最后，序列s的4錯線性復雜度c4（s）＝25，對應的誤差向量為error，利用Berlekamp-Massey算法容易驗證s＋error的線性復雜度確實為25.

5 結語

在魏－董－肖算法的基礎上，首先改寫GF（q）上pn周期序列的k錯線性復雜度快速算法，給出了其m緊錯線性復雜度算法；然后給出計算其誤差向量的有效算法，即在此誤差向量下，能夠實現(xiàn)原序列的k錯線性復雜度ck（s）.其中p和q都是奇素數(shù)，并且q是模p2的一個本原根.

［1］ MASSEY J L.Shift Register Synthesis and BCH Decoding［J］.IEEE Transactions on Information Theory，1969，1 5（1）：122－127.

［2］ BLACKBURN S R.Fast Rational Interpolation，Reed-Solomon Decoding and the Linear Complexity Profiles of Sequences［J］.IEEE Transactions on Information Theory，1997，43（2）：537－548.

［3］ DING Cun-sheng，XIAO Guo-zhen，SHAN Wei-juan.The Stability Theory of Stream Ciphers［M］.LNCS 561.Berlin：Springer-Verlag，1991：85－88.

［4］ STAMP M，MARTIN C F.An Algorithm for the k-Error Linear Complexity of Binary Sequences with Period 2n［J］.IEEE Transactions on Information Theory，1993，39（4）：1 398－1 401.

［5］ KUROSAWA K，SATO F，SAKATA T，et al.A Relationship Between Linear Complexity and k-Error Linear Complexity［J］.IEEE Transactions on Information Theory，2000，46（2）：694－698.

［6］ ZHOU Jian-qin，CHENG Shang－guan，ZHAO Ze-mao.Computing the m-Tight Error Linear Complexity of Periodic Binary Sequences［J］.IEEE Computer Society，CIS 2009，2009：386－390.

［7］ 周建欽，上官成，趙澤茂.若干二元周期序列的緊錯線性復雜度［J］.計算機工程與應用，2011，47（10）：49－53.

［8］ 魏仕民，肖國鎮(zhèn)，陳 鐘.確定周期為2npm二元序列線性復雜度的快速算法［J］.中國科學：E輯，2002，32（3）：401－408.

［9］ 徐喜榮，周建欽.關于求周期序列k錯線性復雜度的Stamp-Martin算法［J］.微電子學與計算機，2007，24（4）：28－31.

［10］ 魏仕民，董慶寬，肖國鎮(zhèn).確定周期序列k－錯線性復雜度的一個快速算法［J］.西安電子科技大學學報，2001，2 8（4）：421－424.

［11］ 白恩鍵，譚示崇，肖國鎮(zhèn).確定周期為pn的q元序列k－錯線性復雜度曲線的一個快速算法［J］.西安電子科技大學學報，2004，31（3）：388－393.

（責任編輯 向陽潔）

On k-Error Linear Complexity of pn-Periodic Sequences over GF（q）

ZHOU Jian-qin1，2，OUYANG Kong-li1
（1.Computer Science School，Anhui University of Technology，Ma’anshan 243002，Anhui China；2.College of Telecommunication，Hangzhou Dianzi University，Hangzhou 310018，China）

Error linear complexity of periodic sequences is an important indicator of the stability of the key stream.First，the algorithm for computing the k-error linear complexity of a sequence with a period pnover GF（q）is rewritten，and an efficient algorithm for m-tight error linear complexity of this sequence is given.Secondly，a method is given for computing an error vector which gives the k-error linear complexity.Here pis an odd prime and qis a primitive root modulus p2.

k-error linear complexity；m-tight linear complexity；error vector

TN911.1；TN918.1

A

10.3969／j.issn.1007－2985.2013.06.012

1007－2985（2013）06－0041－06

2013－04－13

安徽省自然科學基金資助項目（1208085MF106）

周建欽（1963－），男，山東巨野人，安徽工業(yè)大學計算機學院教授，主要從事理論計算機科學、密碼學研究.