GF（q）上pn－周期序列的k錯(cuò)線性復(fù)雜度＊

周建欽，歐陽孔禮

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

GF（q）上pn－周期序列的k錯(cuò)線性復(fù)雜度＊

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

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

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

k錯(cuò)線性復(fù)雜度；m緊錯(cuò)線性復(fù)雜度；誤差向量

1 相關(guān)定義

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

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

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

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

定義4［6－7］序列s的m緊錯(cuò)線性復(fù)雜度記為（km，cm），其中km表示序列k錯(cuò)線性復(fù)雜度的第m個(gè)下降點(diǎn)，cm表示km錯(cuò)線性復(fù)雜度.

若有周期序列s，顯然，當(dāng)m＝0時(shí)，c0即為原序列s的線性復(fù)雜度；當(dāng)m＝1時(shí)，k1即為minerror（s），c1為序列s的k1錯(cuò)線性復(fù)雜度.

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

圖1 k錯(cuò)線性復(fù)雜度曲線

圖2 m緊錯(cuò)線性復(fù)雜度曲線

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

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

2 改寫的k錯(cuò)線性復(fù)雜度快速算法

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

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

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

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

最終可得周期序列s的k錯(cuò)線性復(fù)雜度ck（s）＝c.

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

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

證明 當(dāng)l＝pn時(shí)，若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緊錯(cuò)線性復(fù)雜度的快速算法

對魏－董－肖算法的改寫，沒有影響算法的結(jié)構(gòu)，而修改后的算法更方便推廣為計(jì)算m緊錯(cuò)線性復(fù)雜度的快速算法.

在上述算法1的基礎(chǔ)上，通過適當(dāng)修改，易求GF（q）上pn周期序列的m緊錯(cuò)線性復(fù)雜度.具體修改如下：

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

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

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

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

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

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

例1 設(shè)s是GF（5）上的周期為81的序列，其第1個(gè)周期s81＝141022134 423301104 001134332 143022134 423301104 001134332 143022134 423301104 001134302，其m緊錯(cuò)線性復(fù)雜度求解過程如下：此時(shí)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緊錯(cuò)線性復(fù)雜度曲線.

若按照魏－董－肖算法來計(jì)算序列的k錯(cuò)線性復(fù)雜度曲線，先后共需要調(diào)用算法82次，得到圖1所示序列s的k錯(cuò)線性復(fù)雜度曲線，而利用算法2只需要11次.文獻(xiàn)［11］也給出了確定pn－周期的q元序列k錯(cuò)線性復(fù)雜度曲線的算法，但是利用文中的算法更易于理解.另外文獻(xiàn)［11］中部分計(jì)算結(jié)果是錯(cuò)誤的：文中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.事實(shí)上，正確結(jié)果為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的線性復(fù)雜度、線性復(fù)雜度每次下降所需要改變的比特?cái)?shù)以及下降后的值，都可由求解m緊錯(cuò)線性復(fù)雜度的過程計(jì)算出來.因此，對于m緊錯(cuò)線性復(fù)雜度的研究具有重要的意義與價(jià)值.

4 誤差向量的計(jì)算

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

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

（ⅴ）start←start－1，l←1，轉(zhuǎn)向（ⅵ）.

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

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

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

例2 五元序列的一個(gè)周期s81＝141022134 423301104 001134332 143022134 423301104 001134332 143022134 423301104 001134302，求4錯(cuò)線性復(fù)雜度c4（s）及對應(yīng)的誤差向量.

最后，序列s的4錯(cuò)線性復(fù)雜度c4（s）＝25，對應(yīng)的誤差向量為error，利用Berlekamp-Massey算法容易驗(yàn)證s＋error的線性復(fù)雜度確實(shí)為25.

5 結(jié)語

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

［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］ 周建欽，上官成，趙澤茂.若干二元周期序列的緊錯(cuò)線性復(fù)雜度［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（10）：49－53.

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

［9］ 徐喜榮，周建欽.關(guān)于求周期序列k錯(cuò)線性復(fù)雜度的Stamp-Martin算法［J］.微電子學(xué)與計(jì)算機(jī)，2007，24（4）：28－31.

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

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

（責(zé)任編輯 向陽潔）

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

安徽省自然科學(xué)基金資助項(xiàng)目（1208085MF106）

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