具有第二下降點(diǎn)8錯(cuò)線性復(fù)雜度的2n周期序列

王喜鳳，周曉明，周建欽

（安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243002）

具有第二下降點(diǎn)8錯(cuò)線性復(fù)雜度的2n周期序列

王喜鳳，周曉明，周建欽

（安徽工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243002）

基于構(gòu)造方法和方體理論，研究以2錯(cuò)線性復(fù)雜度為第一下降點(diǎn)并以8錯(cuò)線性復(fù)雜度為第二下降點(diǎn)的周期為2n的二元序列，分析第一下降點(diǎn)與第二下降點(diǎn)的關(guān)系；并給出所有可能的8錯(cuò)線性復(fù)雜度的取值形式，同時(shí)推導(dǎo)出以2錯(cuò)線性復(fù)雜度為第一下降點(diǎn)并以8錯(cuò)線性復(fù)雜度為第二下降點(diǎn)的2n周期二元序列的完整的計(jì)數(shù)公式。使用文中方法，同樣也可給出其他以k錯(cuò)線性復(fù)雜度第二下降點(diǎn)或第三下降點(diǎn)的二元序列相關(guān)性質(zhì)。

周期序列；線性復(fù)雜度；k錯(cuò)線性復(fù)雜度；方體理論

作為衡量密鑰流序列強(qiáng)度的一個(gè)重要指標(biāo)，周期序列的線性復(fù)雜度在研究流密碼的安全性方面有很重要的意義。將能夠產(chǎn)生序列s的最短的LFSR（線性反饋移位寄存器）的級(jí)數(shù)定義為s的線性復(fù)雜度，記為L（s），可由Games-Chan算法[1]計(jì)算。

線性復(fù)雜度高的序列并不一定保證序列是安全的，有些序列的線性復(fù)雜度極不穩(wěn)定，若改變其一個(gè)周期中的若干個(gè)元素，會(huì)使這些序列的線性復(fù)雜度發(fā)生很大的變化，此種序列仍然屬于密碼學(xué)上的弱序列。我國學(xué)者丁-肖-單[2]最先注意到這個(gè)問題，因而提出了流密碼的穩(wěn)定性理論，并提出了重量復(fù)雜度、球體復(fù)雜度等流密碼穩(wěn)定性度量指標(biāo)。國外學(xué)者Stamp和Martin[3]隨后引入了類似“球體復(fù)雜度”的錯(cuò)線性復(fù)雜度Lk（s）：設(shè)序列s是周期為N的q元序列，當(dāng)改變s一個(gè)周期中至多k（0≤k≤N）位，得到所有序列的線性復(fù)雜度中的最小值，可由B-M算法[4]及其改進(jìn)算法計(jì)算，并引入了k錯(cuò)線性復(fù)雜度曲線的概念。

關(guān)于k錯(cuò)線性復(fù)雜度下降點(diǎn)，Etzion[5]提出了關(guān)鍵錯(cuò)誤線性復(fù)雜度分布CELCS（critical error linear complexity spectrum）。CELCS由一系列關(guān)鍵錯(cuò)誤點(diǎn)（k，Lk（s））構(gòu)成，滿足Lk（s）＞Lh（s），k＜h，序列線性復(fù)雜度的下降只發(fā)生在這些關(guān)鍵錯(cuò)誤點(diǎn)處。對(duì)第一次下降點(diǎn)已有許多學(xué)者進(jìn)行了研究，如文獻(xiàn)[6-7]。

文中研究以2錯(cuò)線性復(fù)雜度為第一下降點(diǎn)并以8錯(cuò)線性復(fù)雜度為第二下降點(diǎn)的周期為2n的二元序列，分析第一下降點(diǎn)與第二下降點(diǎn)的關(guān)系，并給出了8錯(cuò)線性復(fù)雜度所有可能的取值，推出滿足已知2錯(cuò)和8錯(cuò)線性復(fù)雜度的序列計(jì)數(shù)公式，并通過計(jì)算機(jī)編程進(jìn)行驗(yàn)證。

1 預(yù)備知識(shí)與引理

設(shè)有限域GF（2）上的兩個(gè)向量X=（x1，x2，…，xn）和Y=（y1，y1，…，yn），則定義X+Y=（x1+y1，x2+y1，…，xn+yn）。文中所涉及的序列均為有限域GF（2）上的序列，其中的運(yùn)算都是模2運(yùn)算。

設(shè)sN為序列s的一個(gè)周期，當(dāng)N=2n時(shí)，sN可記為s（n），以下討論的都是周期為2n的二元序列。周期為N的序列s的Hamming重量定義為在s的每個(gè)周期中非零元素的個(gè)數(shù)，記為WH（s）。序列中兩元素間距離指的是兩個(gè)元素的下標(biāo)之差，如周期為N序列，則元素si，sj的距離為（j-i），其中0≤i＜j≤N。

引理1設(shè)周期為N=2n的二元序列s（n），其線性復(fù)雜度L（s（n））=2n，當(dāng)且僅當(dāng)該序列一個(gè)周期中的Hamming重量為奇數(shù)。

引理2[8]設(shè)N（L）為線性復(fù)雜度為L的周期為2n的二元序列的個(gè)數(shù)，則當(dāng)L=0時(shí)，N（L）=1；當(dāng)1≤L≤2n時(shí)，N（L）=2L-1。

引理3已知序列s1（n）和s2（n）是周期為2n的二元序列，若L（s1（n））≠L（s2（n）），則有L（s1（n）+s2（n））= max｛ L（s1（n）），L（s2（n））｝；若L（s1（n））=L（s2（n）），則有L（s1（n）+s2（n））＜L（s1（n））。

設(shè)s是一個(gè)序列，s的k錯(cuò)線性復(fù)雜度為c，e為Hamming重量為k的誤差序列，可假設(shè)s=t+e，L（t）=c。文中研究周期為2n的二元序列s的k錯(cuò)線性復(fù)雜度的若干性質(zhì)，為此引入重要框架：設(shè)集合S=｛t|L（t）=｝c，E=｛e|WH（e）=k｝，SE=｛t+e|t∈S，e∈E｝，其中t是線性復(fù)雜度為c的序列，最終從序列SE中篩選滿足Lk（t+e）=c的序列t+e。

對(duì)于給定的線性復(fù)雜度c，在求滿足Lk（t+e）=c的序列t+e的過程中需排除兩類序列：第一類序列是t+ u∈SE，但Lk（t+u）＜c；第二類序列是x+u，y+v∈SE，Lk（x+u）=Lk（y+v）=c，且x=y，u=v，但x+u=y+v，其中x，y∈S，u，v∈E。

對(duì)于Lk（t+u）＜c的情況，相當(dāng)于存在序列v，使Lk（t+u）=Lk（t+u+v）＜c。因?yàn)長（t）=c，由引理3知，L（u+v）= c，等價(jià)于檢查是否存在序列v，使L（u+v）=c。

對(duì)于Lk（x+u）=Lk（y+v）=c，且x+u=y+v的情況。因x+u=y+v，則x+y=u+v；又因L（x）=L（y）=c，由引理3可知，L（x+y）＜c，則L（u+v）＜c，等價(jià)于檢查是否存在序列v，使L（u+v）＜c，其中WH（u）=WH（v）=k。若存在這樣的序列v，則統(tǒng)計(jì)v的個(gè)數(shù)。

2 具有第二下降點(diǎn)8錯(cuò)線性復(fù)雜度的2n周期二元序列計(jì)數(shù)

該節(jié)中，首先介紹方體理論[9]的相關(guān)知識(shí)。接著研究序列k錯(cuò)線性復(fù)雜度的第一下降點(diǎn)與第二下降點(diǎn)的關(guān)系，給出k錯(cuò)線性復(fù)雜度的所有可能取值形式，并推出以2錯(cuò)線性復(fù)雜度為第一下降點(diǎn)并以8錯(cuò)線性復(fù)雜度為第二下降點(diǎn)的周期為2n的二元序列s（n）的計(jì)數(shù)公式。

定義1設(shè)序列s中兩個(gè)非零元素的位置之差為（2x+1）2y，其中x和y均為整數(shù)，則稱這兩個(gè)元素的距離為2y；若這兩個(gè)元素組成一條邊，則稱邊長為2y；若這兩個(gè)元素組成一條棱，則稱棱長為2y。

定義2設(shè)周期為2n的二元序列s中有2m個(gè)非零元素，0≤i1＜i2＜…＜im＜n。若m=1，則s中有2個(gè)非零元素，且距離為2i1，稱為1方體。若m=2，則s中有4個(gè)非零元素組成一個(gè)矩形，邊長分別為2i1和2i2，稱為2方體。一般情況，s中有2m-1個(gè)非零元素組成（m-1）方體，余下2m-1個(gè)非零元素也組成（m-1）方體，且2m-1對(duì)元素之間的距離均為2im，則稱序列s稱為m方體，且稱序列s的線性復(fù)雜度為方體的線性復(fù)雜度。

定理1設(shè)序列s是周期為2n的二元序列，序列中非零元素組成一個(gè)m方體，棱長分別為2i1，2i2，…，2im，0≤i1＜i2＜…＜im＜n，則線性復(fù)雜度L（s）=2n-（2i1+2i2+…+2im）。

定理2已知周期為2n的二元序列s（n），且L（s（n））＜2n。

（1）L8（s（n））＜L7（s（n））=L6（s（n））=…=L2（s（n））＜L1（s（n））=L（s（n）），當(dāng)且僅當(dāng)s（n）可分解為若干方體c1，c2，c3，…，cn，L（c1）＞L（c2）＞L（c3）…＞L（cn），其中c1為1方體，c2為3方體，且c1和c2的非零元素均不相交，或有一個(gè)重合；（2）L8（s（n））＜L7（s（n））=L6（s（n））=…=L2（s（n））＜L1（s（n））=L（s（n）），當(dāng)且僅當(dāng)L2（s（n））=2n-（2j1+2j2+2j3），0≤j1＜j2＜j3＜n，且L2（s（n））≠2n-（1+2+22）。

證明（1）①必要性：當(dāng)1方體c1和3方體c2中的非零元素互不相交時(shí)，去掉c1中的所有非零元素，或當(dāng)c1和c2中有一個(gè)非零元素重合時(shí)，在重合位置為c2的補(bǔ)一個(gè)非零元素，此時(shí)，c2是s（n）的2錯(cuò)線性復(fù)雜度序列的最大方體。由Kurosawa[6]知，對(duì)周期為2n的二元序列s（n）的Lk（s（n））嚴(yán)格小于L（s（n））=2n-（2i1+2i2+…+ 2im）的k的最小值kmin=2m。又因c2是3方體，則L2（s（n））=L4（s（n））=L6（s（n））。當(dāng)c1和c2的非零元素互不相交時(shí)，在c1上增加6個(gè)非零元素，使c1變?yōu)榕cc2同類型的3方體，則c1，c2可構(gòu)成一個(gè)4方體。因此，s（n）的8錯(cuò)線性復(fù)雜度序列最大的方體為4方體，線性復(fù)雜度下降，即L8（s（n））＜L2（s（n））。當(dāng)c1與c2中的非零元素有一個(gè)重合時(shí)，將c1+c2中8個(gè)非零元素均變?yōu)榱闼?，此時(shí)c3是s（n）的8錯(cuò)線性復(fù)雜度序列中的最大方體，則L8（s（n））＜L2（s（n）），線性復(fù)雜度同樣會(huì)下降。

②充分性：假設(shè)c1，c2與c3均是1方體，其中非零元素互不相交，且在c1，c2，c3中增加2個(gè)元素，不能構(gòu)成3方體。當(dāng)c1與c2的非零元素互不相交時(shí)，將c1和c2的非零元素變?yōu)榱?，線性復(fù)雜度下降，L4（s（n））＜L2（s（n））與L2（s（n））=L4（s（n））矛盾，則此情況不存在。

假設(shè)c1是1方體，c2是2方體，c1與c2的非零元素既可以不相交，也可有一個(gè)重合。當(dāng)c1與c2的非零元素不相交時(shí)，去掉c1和c2的非零元素，則線性復(fù)雜度下降，即L6（s（n））＜L2（s（n）），與已知條件矛盾。當(dāng)c1和c2有一個(gè)非零元素重合時(shí)，去掉c1+c2中的非零元素，則線性復(fù)雜度下降，即L4（s（n））＜L2（s（n）），與已知條件矛盾。

假設(shè)c1是1方體，c2是4方體，c1與c2的非零元素既可以不相交，也可以有一個(gè)重合。因c2是4方體，需改變至少16個(gè)元素線性復(fù)雜度才可能會(huì)下降，與L8（s（n））＜L2（s（n））矛盾。

綜上所述，只有c1為1方體，且c2為3方體的情況滿足已知條件。

（2）由（1）易知，L8（s（n））＜L2（s（n））＜L（s（n）），當(dāng)且僅當(dāng)L2（s（n））=2n-（2j1+2j2+2j3），其中0≤j1＜j2＜j3＜n。接著證明L2（s（n））≠2n-（1+2+22），因c1為1方體，c2為3方體，若L（c2）=2n-（1+2+22），則L（c1）=2n-1或2n-2或2n-22，則方體c1，c2中各存在1個(gè)非零元素，使得這兩個(gè)元素間的距離d＞22。假設(shè)L2（s（n））=2n-（2j1+2j2+2j3），則2j3≥d＞ 22，可得L2（s（n））≠2n-（1+2+22）。

下面研究以2錯(cuò)線性復(fù)雜度為第一下降點(diǎn)并以8錯(cuò)線性復(fù)雜度第二下降點(diǎn)的周期為2n的二元序列的L8（s（n））的所有可能取值情況。

定理3設(shè)序列s（n）為周期為2n的二元序列，如果L8（s（n））＜L2（s（n））＜L（s（n）），且L（s（n））=2n-2i0，L2（s（n））=2n-（2j1+2j2+2j3），0≤j1＜j2＜j3＜n，則

證明以下證明基于框架：SE={t+e|t∈S，e∈E}，其中L（t）=L8（s（n）），WH（e）=8，L2（e）=2n-（2j1+2j2+2j3）。使用篩選法，從SE中篩選出L8（t+e）=L的序列t+e。

（1）當(dāng)L8（s（n））=2n-（2i1+2i2+…+2im），m＞4時(shí)，s（n）的8錯(cuò)線性復(fù)雜度序列中有2m個(gè)非零元素。關(guān)于Lk（t+u）＜c的情況，等價(jià)于存在序列v，使得L（u+v）=c。因WH（u）=WH（v）=8，則序列u+v的最多有16個(gè)元素，小于2m，所以L（u+v）不可能等于L8（s（n）），即不存在序列v，使得L（u+v）=L8（s（n））。

（2）當(dāng)L8（s（n））=2n-（2i1+2i2+2i3+2i4）時(shí)，

①用反證法證明L8（s（n））=2n-（2i1+2i2+2i3+2i4），其中{i1，i2，i3，i4}≠{j1，j2，j3，j4}。假設(shè)n=5，i0=1，j1=0，j2=2，j3=4，u（5）={1110 1100 0000 0000 0100 1100 0000 0000}，則存在序列v（5）={0001 0011 0000 0000 1011 0011 0000 0000}，使得u（5）+v（5）={1111 1111 0000 0000 1111 1111 0000 0000}，則L（u（5+v（5））=2n-（2j1+2i0+2j2+2j3）=25-（1+ 2+4+16）＜L=L8（s（n）），因此，L8（s（n））≠2n-（2i1+2i2+2i3+2i4），其中{i1，i2，i3，i4}={j1，i0，j2，j3}。

用型號(hào)為XRF-1800X的射線熒光光譜儀，對(duì)AE44雷達(dá)外殼本體試樣進(jìn)行元素定量分析；用型號(hào)為HB-3000B布氏硬度計(jì)，測(cè)試AE44雷達(dá)外殼的宏觀硬度；用型號(hào)為CMT5105電子萬能試驗(yàn)機(jī)，測(cè)試試樣的拉伸性能；用型號(hào)為MR2000型金相顯微鏡，觀察試樣的顯微組織；用型號(hào)為D/MAX2500V的X射線衍射儀，對(duì)試樣的物相組成進(jìn)行分析；用型號(hào)為JSM-6490LV掃描電子顯微鏡拍試樣掃描照片，并且用與之匹配的INCA能譜儀對(duì)相應(yīng)位置進(jìn)行成分定性和定量分析．

②用反證法證明L8（s（n））=2n-（2i1+2i2+2i3+2i4），其中{i1，i2，i3，i4}≠{0，1，2，3}，即L8（s（n））=25-（20+21+22+23）。

因?yàn)?，L8（s（n））＜2n-（2j1+2j2+2j3）＜2n-2i0，則2i0＜2j1+2j2+2j3＜1+2+4+8。

假設(shè)L（t）=25-（20+21+22+23），對(duì)任意u∈E有L2（t+u）=2n-（2j1+2j2+2j3），易證L8（t+u）＜2n-（20+21+22+23）。

（3）當(dāng)L8（s（n））=2n-（2i1+2i2+2i3）時(shí)，下面使用反證法證明{j2，j3}{i1，i2，i3}，即證{j2，j3，x}≠{i1，i2，i3}，其中x為一正整數(shù)，0≤x＜n，x≠j2，j3。

假設(shè)s5是周期為25的二元序列，且L（s（5））＜25。若L（s（5））=2n-2i0=25-1，L2（s（5））=25-（2+22+23），則L8（s（5））≠2n-（2j2+2j3+2x）=25-（22+23+2x）。

設(shè)L8（s（5））=25-（22+23+2x），當(dāng)x=0，1時(shí)，L8（s（n））＞L2（s（n）），則x只能取4。根據(jù)框架SE={t+e|t∈S，e∈E}，使S={t|L（t）=25-（2+23+24）}，E={e|WH（e）=8}，最后根據(jù)篩選法從集合SE中篩選出滿足L8（t+e）=25-（2+23+24）的序列t+e。

現(xiàn)考慮s+u∈SE，L8（s+u）＜25-（22+23+24）的情形，等價(jià)于檢查是否存在序列v∈E，使得L（u+v）=25-（22+ 23+24）。

若已知序列u={1110 1010 0000 0000 0010 1010 0000 0000}，則存在一個(gè)序列v={1100 1000 0010 0000 1000 0010 0010}∈E，使L（u+v）=25-（22+23+24），則L8（u+v）＜25-（22+23+24）。又L2（t+v）=25-（2+22+23），則{i1，i2，i3}≠{j2，j3，x}，即{j2，j3}{i1，i2，i3}。同理可得，{j1，j2}{i1，i2，i3}，{j1，j3}{i1，i2，i3}。

定理4設(shè)s（n）為周期為2n的二元序列，且L（s（n））=2n-2i0

（1）若L8（s（n））＜L2（s（n））＜L（s（n）），其中L2（s（n））=2n-（2j1+2j2+2j3），0≤j1＜j2＜j3＜n，

則滿足以上條件的周期為2n的二元序列s（n）的個(gè)數(shù)為

其中，當(dāng)L8（s（n））=2n-（2i1+2i2+2i3+2i4）時(shí)，im=i4；當(dāng)L8（s（n））=2n-（2i1+2i2+2i3）時(shí)，im=i3；L=L8（s（n））；，，。

（2）如果L8（s（n））=0，則N（s（n））=28n-3j3-2j2-j1-i0-11/γ。

證明令S={t|L（t）=L}，E={e|WH（e）=8}，SE={t+e|t∈S，e∈E}，其中序列t的線性復(fù)雜度，序列e滿足L2（e）=2n-（2j1+2j2+2j3）及WH（e）=8。最后，從集合SE中篩選出滿足L8（t+e）=L的序列t+e。

（1）由引理2可知，線性復(fù)雜度L（t）=L的周期為2n的二元序列的個(gè)數(shù)2L-1。

（2）以下證明滿足條件WH（e）=8和L2（e）=2n-（2j1+2j2+2j3）的序列e的個(gè)數(shù)為N（e）=28n-3j3-2j2-j1-i0-11/γ。

①假設(shè)s（j1）是周期為2j1的二元序列，若L（s（j1））=2j1，WH（s（j1））=1，則序列s（j1）的個(gè)數(shù)為N（s（j1））=2j1；

②若j2＞j1，周期為的二元序列s（j2），L（s（j2））=2n-2j1=2j2-2j1，WH（s（j2））=2，因L（s（j2））-L（s（j1+1））=（2j2-2j1）-（2j1+1-2j1）=2j2-1+2j2-2+…+2j1+1有（j2-j1-1）項(xiàng)，則序列s（j2）的個(gè)數(shù)為N（s（j2））=（22）j2-j1-1×N（s（j1+1））=（22）j2-j1-1×2j1= 22j2-j1-2；

因此，滿足L（s（j2+1））=2n-（2j1+2j2）=2j2+1-（2j1+2j2）=2j2-2j1，WH（s（j2+1））=4的周期為2j2+1的二元序列s（j2+1）的個(gè)數(shù)為N（s（j2+1））=N（s（j2））=22j2-j1-2；

③若j3＞j2＞j1，則周期為的二元序列s（j3），滿足，又因多項(xiàng)式L（s（j3））-L（s（j2+1））=2j3-1+2j3-2+…+2j3+1共有（j3-j2-1）項(xiàng)，則序列s（j3）的個(gè)數(shù)為N（s（j3））=（24）j3-j2-1×N（s（j2+1））=（24）j3-j2-1×22j2-j1-2= 24j3-2j2-j1-6；

因此，滿足L（s（j3+1））=2j3+1-（2j1+2j2+2j3）=2j3-2j2-2j1，WH（s（j3+1））=8的周期為2j3+1的二元序列s（j3+1）的個(gè)數(shù)為N（s（j3+1））=N（s（j3））=24j3-2j2-j1-6。

由上可知，滿足e∈E，L2（e）=2n-（2j1+2j2+2j3）的序列e的個(gè)數(shù)為N（e）=24j3-2j2-j1-6，則滿足u∈E，L2（u）=2n-（2j1+2j2+2j3）的序列u的個(gè)數(shù)為。

其中，當(dāng)i0＜j2時(shí)，γ=1；當(dāng)i0＞j2時(shí)，γ=2。

下面舉例說明當(dāng)i0＞j2時(shí)，γ=2。假設(shè)n=4，i0=2，j1=0，j2=1，j3=3，u（4）={1111 1000 0111 0000}，則移動(dòng)u（4）中的非零元素得，使。

接著舉例說明當(dāng)i0＞j2時(shí)，γ=1。假設(shè)n=4，i0=1，j1=0，j2=2，j3=3，u（4）={1110 1100 0100 1100}，則由序列u（4）移動(dòng)相應(yīng)的非零元素僅能找到唯一的序列，v（4）={1100 1100 1100 1100}，使L（v（4））=24-（20+21+23）。

（3）因s+u，t+v∈SE，L8（s+u）=L8（t+v）=L，其中s≠t，u≠v但s+u=t+v，檢查是否存在序列v，WH（u）=WH（v）=8，使L（u+v）=L（s+t）＜L，若存在，則統(tǒng)計(jì)滿足條件的序列v的個(gè)數(shù)。

①情形一：對(duì)于i0

對(duì)于?u∈E，存在1個(gè)序列v，使L（u+v）=2n-（2j1+2i0+2j2+2j3）＜L，即δ=1；存在3個(gè)序列v，使L（u+v）=2n-（2j2+2i0+2j3）＜L，即δ=2；存在7個(gè)序列v，使L（u+v）=2n-（2j1+2i0+2j3）＜L，即δ=3；存在15個(gè)序列v，使L（u+v）= 2n-（2i0+2j3）＜L，即δ=4。

②情形二：對(duì)于im＜ω＜n

對(duì)于im＜ω＜n，存在255×（28）ω-im-1個(gè)序列v，使2n-（2j2+2j3+2ω）＜L，或2n-（2j1+2j3+2ω）＜L，或2n-（2j3+2ω）＜L，或2n-（2j2+2j2+2ω）＜L，或2n-（2j2+2im+2ω）＜L，或2n-（2j1+2ω）＜L，或2n-（2i0+2ω）＜L，或2n-2ω＜L。

對(duì)任意有8個(gè)非零元素的序列v，周期翻倍且非零元素個(gè)數(shù)不變時(shí)，可得28個(gè)新序列。因此，存在255+ 255×28+…+255×（28）n-im-2=（28）n-im-1-1個(gè)序列v，使L（u+v）＜L。

因此，存在（28）n-im-1-1=（28）n-i3-1-1=（28）6-4-1-1=255個(gè)序列v，使L（u+v）＜L。當(dāng)j3＜im，且僅2n-（2j2+2j3+2im）＜L時(shí)，序列v以1×（28）n-im-1遞增，即ε=1；當(dāng)2n-（2j2+2j3+2im）＜L時(shí)，序列v以3×（28）n-im-1遞增，即ε=2；當(dāng)時(shí)，序列v以7×（28）n-im-1遞增，即ε=3；當(dāng)2n-（2j3+2im）＜L時(shí)，序列v以15×（28）n-im-1遞增，即ε=4；當(dāng)時(shí)，序列v以31×（28）n-im-1遞增，即ε=5；當(dāng)2n-（2j2+2im）＜L時(shí)，序列v以63×（28）n-im-1遞增，即ε=6；當(dāng)2n-（2j1+2im）＜L時(shí)，序列v以127×（28）n-im-1遞增，即ε=7。

因?yàn)椋?dāng)δ＞0時(shí)，2n-（2j1+2j2+2i0+2j3）＜L＜L2（s（n））=2n-（2j1+2j2+2j3），即2n-（2j1+2j2+2i0+2j3）＜2n-（2i1+2i2+…+2im）＜2n-（2j1+2j2+2j3），則j3=im；又因當(dāng)ε＞0時(shí)，j3＜im。所以δ，ε不能同時(shí)為正整數(shù)，即δ，ε中至少有一個(gè)為0。

特殊地，當(dāng)ε=0，且δ=0時(shí)，對(duì)于?u∈E，j2＜ξ＜j3，存在1個(gè)序列v，使L（u+v）=2n-（2j2+2ξ+2j3）＜L，即λ＝1；存在2個(gè)序列v，使L（u+v）=2n-（2j1+2ξ+2j3）＜L，即λ＝2。

為了進(jìn)一步驗(yàn)證定理4，下面舉出一個(gè)例子，其正確性已用計(jì)算機(jī)程序進(jìn)行了驗(yàn)證。

例1n=5，i0=2，j1=0，j2=1，j3=3，i1=0，i2=1，i3=2，i4=4。L=L8（s（n））=2n-（2i1+2i2+2i3+2i4

）=25-（1+2+4+16）=9，因i0＞j2，則γ=2；因2n-（2j1+2j2++2i0+2j3）=25-（1+2+4+8）=17＞L，則δ=0；又因j3＜i4，且2n-（2j3+2im）=25-（8+16）=8＜L，則ε=3；因ε≠0，δ=0，則λ=0，則滿足L（s（5））=28，L2（s（5））=21，L8（s（5））=9的周期為25的二元序列s（5）的個(gè)數(shù)為

3 結(jié)語

文中給出以8錯(cuò)線性復(fù)雜度為第二下降點(diǎn)的所有可能取值形式，并推出具有2錯(cuò)線性復(fù)雜度和8錯(cuò)線性復(fù)雜度序列的完整計(jì)數(shù)公式。據(jù)文中的研究方法，可對(duì)其他具有第二下降點(diǎn)錯(cuò)線性復(fù)雜度序列進(jìn)行研究，如k=6，其中2錯(cuò)線性復(fù)雜度為第一下降點(diǎn)，且6錯(cuò)線性復(fù)雜度為第二下降點(diǎn)。亦可研究以錯(cuò)線性復(fù)雜度為第三下降點(diǎn)的周期序列，如k=5，即以1錯(cuò)線性復(fù)雜度為第一下降點(diǎn)，3錯(cuò)復(fù)雜度為第二下降點(diǎn)，5錯(cuò)復(fù)雜度為第三下降點(diǎn)。

[1]Games R A，Chan A H.A fast algorithm for determining the complexity of a binary sequence with period 2n[J].IEEE Trans on Information Theory，1983，29（1）：144-146.

[2]Ding C S，Xiao G Z，Shan W J.The Stability Theory of Stream Ciphers[M].Berlin/Heidelberg，Germany：Springer-Verlag，1991：85-88.

[3]Stamp M，Martin C F.An algorithm for the k-error linear complexity of binary sequences with period 2n[J].IEEE Trans.Inform.Theory，1993，39：1398-1401.

[4]Massey J L.Shift register synthesis and BCH decoding[J].IEEE Trans on Information Theory，1969，15（1）：122-127.

[5]Etzion T，Kalouptsidis N，Kolokotronis N，et al.Properties of the error linear complexity spectrum[J].IEEE Transactions on Information Theory，2009，55（10）：4681-4686.

[6]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.

[7]皮飛，戚文峰.二元周期序列的4-錯(cuò)線性復(fù)雜度[J].電子學(xué)報(bào)，2011，39（12）：2914-2920.

[8]Meidl W.How many bits have to be changed to decrease the linear complexity?[J].Des Codes Cryptogr，2004，33：109-122.

[9]Zhou J Q，Liu W Q.On the k-error linear complexity for 2n-periodic binary sequences via Cube Theory[EB/OL].[2013-09-07].http://arxiv.org/ abs/1309.1829.

2n-periodic binary sequences with 8-error linear complexity as the second descent point

WANG Xifeng，ZHOU Xiaoming，ZHOU Jianqin
（School of Computer Science&Technology，Anhui University of Technology，Ma'anshan 243002，China）

Based on the structural approach and cube theory，we investigated the 2n-periodic binary sequences with 2-error linear complexity as the first descent point and 8-error linear complexity as the second descent point and analyzed the relationship between the first descent point and the second descent point.All the possible values of the 8-error linear complexity were given.Then we derived the complete counting functions of 2nperiodic binary sequences with 2-error linear complexity as the first descent point and 8-error linear complexity as the second descent point.With this method，2n-periodic binary sequences with k-error linear complexity as the second or third descent point can be obtained.

periodic sequence；linear complexity；k-error linear complexity；cube theory

TN918.1

A

1672-0687（2015）02-0056-09

責(zé)任編輯：艾淑艷

2014-05-06

安徽省自然科學(xué)基金資助項(xiàng)目（1208085MF106）；安徽省教育廳自然科學(xué)研究項(xiàng)目（KY2013Z025）；國家自然科學(xué)基金資助項(xiàng)目（61300059）

王喜鳳（1980-），女，山東成武人，講師，碩士，研究方向：通信，密碼學(xué)與理論計(jì)算機(jī)科學(xué)。