4錯(cuò)線性復(fù)雜度的2n周期序列計(jì)數(shù)

畢松松，戴小平

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

4錯(cuò)線性復(fù)雜度的2n周期序列計(jì)數(shù)

畢松松，戴小平

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

k錯(cuò)線性復(fù)雜度是衡量序列密碼穩(wěn)定性的重要指標(biāo)之一。給出求滿足4錯(cuò)線性復(fù)雜度的2n周期序列計(jì)數(shù)的過程。把4錯(cuò)線性復(fù)雜度的研究分解為對關(guān)鍵錯(cuò)誤線性復(fù)雜度的研究，再用方體理論和篩選法討論關(guān)鍵錯(cuò)誤線性復(fù)雜度，得到相應(yīng)關(guān)鍵錯(cuò)誤點(diǎn)（下降點(diǎn)）4錯(cuò)線性復(fù)雜度的取值形式，及此時(shí)二元序列精確計(jì)數(shù)公式。最后，歸納出4錯(cuò)線性復(fù)雜度所有的取值形式和計(jì)算出滿足4錯(cuò)線性復(fù)雜度的序列計(jì)數(shù)。

關(guān)鍵錯(cuò)誤線性復(fù)雜度；k錯(cuò)線性復(fù)雜度；方體理論；篩選法

流密碼是現(xiàn)代密碼學(xué)的一個(gè)重要分支，研究具有高強(qiáng)度的流密碼序列一直是密碼學(xué)的重要工作之一。高強(qiáng)度的密碼序列s要求序列具有高的線性復(fù)雜度L（s）和穩(wěn)定的k錯(cuò)線性復(fù)雜度Lk（s）。k錯(cuò)線性復(fù)雜度是指當(dāng)改變序列一個(gè)周期中至多k比特后，得到的所有序列中最小的線性復(fù)雜度。

已知L（s）或Lk（s），求滿足s的計(jì)數(shù)。文獻(xiàn)［4］給出2n周期序列3錯(cuò)線性復(fù)雜度的完整序列計(jì)數(shù)公式。Meidl［5］給出2n周期二元序列1錯(cuò)線性復(fù)雜度和2錯(cuò)線性復(fù)雜度的分布情況。

給出求滿足4錯(cuò)線性復(fù)雜度的2n周期序列計(jì)數(shù)的過程。其研究方法不同于文獻(xiàn)［2，4-5］。通過把4錯(cuò)線性復(fù)雜度的研究分解為對關(guān)鍵錯(cuò)誤線性復(fù)雜度的研究，再使用方體理論和篩選法討論關(guān)鍵錯(cuò)誤線性復(fù)雜度，最后得到滿足4錯(cuò)線性復(fù)雜度的序列計(jì)數(shù)。

1 預(yù)備知識(shí)

設(shè)在有限域GF（2）域上有兩序列x=（x1，x2，…，xn）和y=（y1，y2，…，yn），定義x+y=（x1+y1，x2+y2，…，xn+yn），其中“+”為異或運(yùn)算或模2加法運(yùn)算。

引理1［7］序列s是以N=2n為周期的二元序列，若L（s）=N，當(dāng)且僅當(dāng)WH（sN）為奇數(shù)。

引理2［7］序列s是以N=2n為周期的二元序列，若L（s）=0，則滿足條件的s的個(gè)數(shù)為1；若L（s）=L，1≤L≤N則滿足條件的s的個(gè)數(shù)為2L-1。

引理3［8］序列s1，s2是以N=2n為周期的兩二元序列，如果L（s1）≠L（s2），則L（s1+s2）=max（L（s1），L（s2））；否則，L（s1+s2）＜L（s1）。

下面給出方體理論的基本內(nèi)容，可參考文獻(xiàn)［6，9-10］。

定義2 序列s是以N=2n為周期的二元序列，設(shè)L（s）=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im＜n，若m=1，s有 2個(gè)非零元素且形成一條邊，邊長為2i1，構(gòu)成一個(gè)1方體；若m=2，s有4個(gè)非零元素且形成一個(gè)矩形，邊長為2i1、2i2，構(gòu)成一個(gè)2方體。一般而言，s中有2m-1個(gè)非零元素構(gòu)成一個(gè)（m-1）方體，s中另外2m-1個(gè)非零元素也構(gòu)成一個(gè)（m-1）方體，這2m-1對元素之間的距離均為2im，則這兩個(gè)（m-1）方體構(gòu)成一個(gè)m方體，2im為這兩個(gè)（m-1）方體的距離。

引理4 序列s是以N=2n為周期的二元序列，L（s）=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im＜n，線性復(fù)雜度第一下降點(diǎn)K=2m。

引理5 序列s是以N=2n為周期的二元序列，若s的非零元素組成一個(gè)m方體，且其邊長為2i1，2i2，…，2im，0≤i1＜i2＜…＜im＜n，則L（s）=2n-（2i1+2i2+…+2im）。

圖1所示是一個(gè)邊長為1，2，4的3方體，其線性復(fù)雜度為2n-（1+2+4）。這個(gè)3方體可由兩個(gè)邊長為1和4的2方體構(gòu)成，且這兩個(gè)2方體之間的距離為2。

下面為篩選法的基本內(nèi)容，可參考文獻(xiàn)［10］。

圖1 引理5示意圖

從TE中篩選出序列t+e，Lk（t+e）=c，需要排除的序列有兩類，第一類是t+e∈TE，但Lk（t+e）＜c。第二類是x+u，y+v∈TE，并且Lk（x+u）=Lk（y+v）=c，x≠y，u≠v，WH（u）=WH（v）=k，但x+u=y+v。

對Lk（t+e）＜c的情況，設(shè)有序列v，WH（v）=k，使得Lk（t+u）=L（t+u+v）＜c。從而，有L（u+v）=c。問題可以轉(zhuǎn)化成檢查是否存在v，使得L（u+v）=c。對第二類的情況，因L（u+v）=c，根據(jù)異或運(yùn)算規(guī)則，有x+y=u+v。而L（x）=L（y）=c，從而L（x+y）＜c，進(jìn)而L（u+v）＜c。問題可以轉(zhuǎn)化為檢查是否存在v，使得L（u+v）＜c。

2 4錯(cuò)線性復(fù)雜度的二元序列計(jì)數(shù)

定義Nk（L）表示周期為2n二元序列s的個(gè)數(shù)，其中Lk（s）=L，0≤k≤2n。

定義Ni，k（L）表示周期為2n二元序列s的個(gè)數(shù)，其中Lk（s）=L，i（0≤i≤k）是序列s線性復(fù)雜度的第一下降點(diǎn)。

周期為N=2n的二元序列s，據(jù)引理1，若WH（sN）為奇數(shù)，則改變s一個(gè)周期的2個(gè)或4個(gè)元素，改變后序列的線性復(fù)雜度仍為2n；若WH（sN）為偶數(shù)，改變s一個(gè)周期的2個(gè)或4個(gè)元素后，線性復(fù)雜度可能下降。

定義Ni，k（c0，c1，L）表示周期為2n二元序列s的個(gè)數(shù)，其中s的線性復(fù)雜度為c0，2錯(cuò)線性復(fù)雜度為c1，4錯(cuò)線性復(fù)雜度為L，i（0≤i≤k）是序列s復(fù)雜度的第一下降點(diǎn)。

那么，滿足L4（s）=L的序列s的個(gè)數(shù)為：N4（L）=N0，4（L）+N2，4（L）+N4，4（L）。若求N4（L），需分別求N0，4（L），N2，4（L）和N4，4（L）。

2.1 線性復(fù)雜度第一下降點(diǎn)k=0的序列計(jì)數(shù)

定理1 設(shè)s（n）是以N=2n為周期的二元序列，若L（s（n））=L2（s（n））=L4（s（n）），那么L4（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im＜n，m≥3。

證明 s（n）是周期為2n的二元序列，其線性復(fù)雜度為L（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im＜n，由引理4，使得Lk（s（n））＜L（s（n））的kmin=2m。 若L（s（n））=L2（s（n））=L4（s（n）），那么2m＞4。 從而，L4（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im＜n，m≥3。

定理2 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））=L2（s（n））=L4（s（n）），其中L4（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im＜n，m≥3。那么滿足條件的二元序列s（n）的個(gè)數(shù)為2L-1。

證明 由引理2可知，L（s（n））=L，若1≤L≤2n，周期為2n的二元序列s（n）的個(gè)數(shù)為2L-1。

2.2 線性復(fù)雜度第一下降點(diǎn)k=2的序列計(jì)數(shù)

線性復(fù)雜度第一下降點(diǎn)k=2，包含2種情況：（1）線性復(fù)雜度第一下降點(diǎn)k=2，第二下降點(diǎn)k＞4；（2）線性復(fù)雜度第一下降點(diǎn)k=2，且第二下降點(diǎn)k=4。

2.2.1 線性復(fù)雜度第一下降點(diǎn)k=2，第二下降點(diǎn)k＞4的序列計(jì)數(shù)

定理3 設(shè) s（n）是以 2n為周期的二元序列，若 L（s（n））＞L2（s（n））=L4（s（n）），那么，L（s（n））=2n-2i，L2（s（n））= L4（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im，m≥3。

證明 s（n）是周期為2n的二元序列，L（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im，若L（s（n））＞L2（s（n）），即2錯(cuò)是線性復(fù)雜度第一下降點(diǎn)，那么L（s（n））=2n-2i；而第二下降點(diǎn)k＞4，那么L2（s（n））=L4（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im，m≥3。

由定理3容易看出，研究線性復(fù)雜度第一下降點(diǎn)k=2，第二下降點(diǎn)k＞4的二元序列，可以通過研究線性復(fù)雜度第一下降點(diǎn)k=2的二元序列得到，但是要排除形如 L2（s（n））=2n-2i和L2（s（n））=2n-（2i+2j）兩種情況。

定理 4 設(shè) s（n）是以 2n為周期的二元序列，若 L（s（n））＞L2（s（n））=L4（s（n）），其中，L（s（n））=2n-2i，L2（s（n））= L4（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im，m≥3。

（1）滿足條件的二元序列s（n）的個(gè)數(shù)為22n-i-2×2L-1/（θ×2ε×2n-im-1）。

如果存在i0（0≤i0＜i），使得2n-（2i0+2i）＜L，那么θ=2i-i0；否則，θ=1。當(dāng)i＜im時(shí)，若2n-（2i+2im）＞L，ε=0；若2n-（2i+2im）＜L＜2n-2im，ε=1。

（2）如果L2（s（n））=0，以周期為2n的二元序列s（n）的個(gè)數(shù)為22n-i-2。

證明 設(shè)TE=｛t+e|t∈T，e∈E｝，T=｛t|L（t）=L｝，其中L（t）=2n-（2i1+2i2+…+2im），并且L（e）=2n-2i。使用篩選法，從TE中篩選出L2（t+e）=L的序列t+e。

（1）由引理2可知，L（t）=L，若1≤L≤2n，周期為2n的二元序列的t個(gè)數(shù)為2L-1；否則，t的個(gè)數(shù)為1。

（2）下面求出e的個(gè)數(shù)，WH（e）=2，L（e）=2n-2i。

設(shè)s（i）是以2i為周期的二元序列，若L（s（i））=2i且WH（s（i））=1，那么序列s（i）的個(gè)數(shù)是2i。周期翻倍，變成2i+1，若線性復(fù)雜度為2i+1-2i=2i且WH（s（i+1））=2，那么s（i+1）的個(gè)數(shù)還是2i。

所以，滿足條件WH（e）=2，L（e）=2n-2i的二元序列e的個(gè)數(shù)為2i×（22）n-i-1=22n-i-2。

（3）由上述可知：當(dāng)L（t）=0時(shí)，t+e的個(gè)數(shù)為22n-i-2，（2）得證；當(dāng)L（t）＞0時(shí)，t+e的個(gè)數(shù)小于22n-i-2×2L-1，因?yàn)榇藭r(shí)t+e的個(gè)數(shù)中存在重復(fù)的情況，即存在s+u，t+v∈TE，L2（s+u）=L2（t+v）=L，其中s≠t，u≠v，但s+u=t+v。排除重復(fù)序列的思想源自篩選法第二類的情況，需要檢查是否存在這樣的v，使得L（u+v）=L（s+t）＜L，以及這時(shí)v的個(gè)數(shù)。其中WH（u）=WH（v）=2，L（u）=L（v）=2n-2i。下面考慮兩種情況。

①跟i0，i有關(guān)

對于?u∈E，若2n-（2i0+2i）＜L，0≤i0＜i，存在2i-i0-1個(gè)v，θ=2i-i0，使得L（u+v）＜L。

下面進(jìn)行舉例說明。

假設(shè)n=4，i=3時(shí)，存在序列u（4）=｛1000 0000 1000 0000｝；

滿足2n-（22+23）=4＜L的v的個(gè)數(shù)為1，v=｛0000 1000 0000 1000｝；

滿足2n-（21+23）=6＜L的v的個(gè)數(shù)為3，v=｛0000 0010 0000 0010｝；v=｛0010 0000 0010 0000｝；

滿足2n-（20+23）=7＜L的v的個(gè)數(shù)為7，v=｛0000 0001 0000 0001｝；v=｛0000 0100 0000 0100｝；v=｛0001 0000 0001 0000｝；v=｛0100 0000 0100 0000｝。

②跟im＜ω＜n有關(guān)

對于im＜ω＜n，存在3×（22）ω-im-1個(gè)序列v，使得L（u+v）=2n-（2i+2ω）＜L或L（u+v）=2n-2ω＜L。

對于滿足任意條件的v有2個(gè)非零元素，若將v的周期加倍，那么一個(gè)原序列將會(huì)產(chǎn)生22個(gè)新序列。將周期變成2n，存在3+3×22+…+3×（22）n-im-2=（22）n-im-1-1個(gè)v，使得L（u+v）＜L。

下面給出例子說明。

假設(shè) n=4，i=0時(shí)，設(shè)有序列 u（4）=｛1100 0000 0000 0000｝，只存在 v=｛0000 0000 1100 0000｝，使L（u（4）+v）=2n-（2i+2ω）=24-（20+23）=7。只存在v=｛0100 0000 1000 0000｝，v=｛1000 0000 0100 0000｝，使得L（u（4）+v）=L（u（4）+v）=2n-2ω=24-23=8。

由上可知，當(dāng)im＜ω＜n時(shí)，在2n-（2i+2im）＜L＜2n-2im時(shí)，v的個(gè)數(shù)增加（22）n-im-1，ε=1。

綜上所述，滿足L（s（n））=2n-2i＞L2（s（n））=L4（s（n））且L4（s（n））=L的2n周期二元序列s（n）的計(jì)數(shù)公式為

當(dāng)i=im或2n-（2i+2im）＞L時(shí)，ε=0；當(dāng)2n-（2i+2im）＜L＜2n-2im時(shí)，ε=1。

如果存在i0，使得2n-（2i0+2i）＜L，0≤i0＜i，那么θ=2i-i0；否則，θ=1。

定理 4已經(jīng)求得在已知 L（s（n））=c0，L（s（n））＞L2（s（n））=L4（s（n））=L時(shí)二元序列 s（n）的計(jì)數(shù)公式。 當(dāng)已知L4（s（n））=L，而未知L（s（n））=c0時(shí)，可以根據(jù)定理3給出的L與c0的約束關(guān)系，從L推測出c0，進(jìn)而得到序列s（n）的計(jì)數(shù)。

例1 若n=4，L（s（n））＞L2（s（n））=L4（s（n））=9，求滿足條件的以24為周期的二元序列s（n）的個(gè)數(shù)。由定理3知，L4（s（n））的線性復(fù)雜度可以由一個(gè)m≥3方體表示，L（s（n））的線性復(fù)雜度只能由一個(gè)1方體表示。因?yàn)閚=4，L4（s（n））=9，可以計(jì)算出L（s（n））的值為12，14或15。所以，當(dāng)L（s（n））＞L2（s（n））=L4（s（n））時(shí)，N2，4（9）=N2，4（12，9，9）+N2，4（14，9，9）+N2，4（15，9，9）=1 024+2 048+4 096=7 168。

2.2.2 線性復(fù)雜度第一下降點(diǎn)k=2，第二下降點(diǎn)k=4的序列計(jì)數(shù)

線性復(fù)雜度第一下降點(diǎn)k=2，第二下降點(diǎn)k=4的二元序列分布，文獻(xiàn)［10］已給出了相關(guān)的結(jié)論和證明。

引理6 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））＞L2（s（n））＞L4（s（n）），那么，L（s（n））=2n-2i0，或者L2（s（n））= 2n-（2i+2j），i0＜i或者i＜i0＜j，但是L2（s（n））≠2n-（20+21）。

引理7 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））＞L2（s（n））＞L4（s（n）），并且L（s（n））=2n-2i0，L2（s（n））=2n-（2i+2j），i0＜i或者i＜i0＜j，L2（s（n））≠2n-（20+21），那么

引理8 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））＞L2（s（n））＞L4（s（n）），并且L（s（n））=2n-2i0，L2（s（n））=2n-（2i+2j），i0＜i或者i＜i0＜j，L2（s（n））≠2n-（20+21），并且

那么，滿足條件的二元序列s（n）的個(gè)數(shù)為（24n-j-i-i0-4）×2L-1/（2δ×2ε×16n-im-1）。

如果i0＞i，γ=2；或則γ=1。若2n-（2i+2i0+2j）＞L，δ=0；若2n-（2i+2i0+2j）＜L＜2n-（2i0+2j），δ=1；若2n-（2i0+2j）＜L，δ=2。當(dāng)j=im或2n-（2j+2im）＞L，ε=0；當(dāng)2n-（2j+2im）＜L＜2n-（2i+2im），ε=1；當(dāng)2n-（2i+2im）＜L＜2n-（2i0+2im），ε=2；當(dāng)2n-（2i0+2im）＜L＜2n-2im，ε=3。

由以上知，L（s（n））＞L2（s（n））＞L4（s（n））時(shí)，若只給出L4（s（n））=L，可以通過相關(guān)約束關(guān)系求出L（s（n））和L2（s（n）），進(jìn)而得到二元序列s（n）的計(jì)數(shù)。

例2 若n=4，L（s（n））＞L2（s（n）），L4（s（n））=5，求滿足條件的以24為周期的二元序列s（n）的個(gè)數(shù)。

如果L（s（n））＞L2（s（n））＞L4（s（n）），由引理8得到L（s（n））=15，L2（s（n））=10；L（s（n））=14，L2（s（n））=11；L（s（n））=12，L2（s（n））=7或L（s（n））=12，L2（s（n））=6。

如果L（s（n））＞L2（s（n））=L4（s（n）），由定理3得到L（s（n））=15；L（s（n））=14；L（s（n））=12；L（s（n））=8。

所以，當(dāng)n=4，L4（s（n））=5，而2錯(cuò)為線性復(fù)雜度第一下降點(diǎn)時(shí)，

N2，4（5）=N2，4（8，5，5）+N2，4（12，5，5）+N2，4（14，5，5）+N2，4（15，5，5）+N2，4（12，6，5）+N2，4（12，7，5）+N2，4（14，11，5）+N2，4（15，10，5）=64+128+512+1 024+128+256+2 048+4 096=8 256

2.3 線性復(fù)雜度第一下降點(diǎn)k=4的序列計(jì)數(shù)

定理5 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））=L2（s（n））＞L4（s（n）），那么L（s（n））=L2（s（n））=2n-（2i+2j）。

證明 s（n）是周期為2n的二元序列，L（s（n））=2n-（2i1+2i2+…+2im），0≤i1＜i2＜…＜im，若4錯(cuò)是線性復(fù)雜度第一下降點(diǎn)，那么L（s（n））=L2（s（n））=2n-（2i+2j）。

定理6 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））=L2（s（n））＞L4（s（n））且有L（s（n））=L2（s（n））=2n-（2i+2j），那么

證明 源自篩選法中的第一類的情況，并構(gòu)造如下框架：設(shè)TE=｛t+e|t∈T，e∈E｝，其中T=｛t|L（t）=L｝，E= ｛e|WH（e）=4｝，使用篩選法，從TE中篩選出滿足L4（t+e）=L的序列t+e?，F(xiàn)研究t+u∈TE，但L4（t+u）＜L=L4（s（n））的情況。這種情況等價(jià)于檢查是否存在v，v∈E，使得L（u+v）=L。對于?u∈E，有L4（u）=L4（s（n））。

當(dāng)L4（s（n））=2n-（2i1+2i2+2i3）＜2n-（2i+2j）時(shí)，使用反證法證明｛i1，i2，i3｝不包含｛i，j｝。設(shè)n=4，i=0，j=2時(shí)，有u（4）=｛1100 1100 0000 0000｝。存在v=｛0000 0000 1100 1100｝，使得L（u+v）=25-（20+22+23），所以有L4（t+u）＜25-（20+22+23），因此，｛i1，i2｝≠｛i，j｝。

同理可得｛i2，i3｝≠｛i，j｝。進(jìn)而，｛i1，i2，i3｝不包含｛i，j｝。

同理有i1≠i，j且i2＞j。

定理7 設(shè)s（n）是以2n為周期的二元序列，若L（s（n））=L2（s（n））＞L4（s（n））且有L（s（n））=L2（s（n））=2n-（2i+2j），其中

（1）滿足條件的二元序列s（n）的個(gè)數(shù)為24n-2j-i-6×2L-1/（θ1×θ2×θ3×2ε×16n-im-1）。

如果存在k0，使得2n-（2i+2k0+2j）＜L，i＜k0＜j，那么θ1=2j-k0；否則，θ1=1。

如果存在k1，使得2n-（2k1+2j）＜L，i＜k1＜j，那么θ2=2j-k1；否則，θ2=1。

如果存在k2，使得2n-（2k2+2i+2j）＜L，0≤k2＜i，那么θ3=2i-k2；否則，θ3=1。

當(dāng)j＜im時(shí)，若2n-（2i+2j+2im）＜L，ε=0；若2n-（2i+2j+2im）＜L＜2n-（2j+2im），ε=1；若2n-（2j+2im）＜L＜2n-（2i+2im），ε=2；若2n-（2i+2im）＜L＜2n-2im，ε=3。

（2）如果L4（s（n））=0，以周期為2n的二元序列s（n）的個(gè)數(shù)為24n-2j-i-6。

證明 設(shè)TE=｛t+e|t∈T，e∈E｝，T=｛t|L（t）=L｝，E=｛e|WH（e）=4｝，其中L（t）=2n-（2i1+2i2+…+2im），并且L（e）= L2（e）=2n-（2i+2j）。使用篩選法，從TE中篩選出L4（t+e）=L的序列t+e。

1）由引理2可知，L（t）=L，若1≤L≤2n，周期為2n的二元序列的t個(gè)數(shù)為2L-1；否則，t的個(gè)數(shù)為1。

2）下面求出e的個(gè)數(shù)，WH（e）=4，L（e）=L2（e）=2n-（2i+2j）。

設(shè)s（i）是以2i為周期的二元序列，若L（s（i））=2i且WH（s（i））=1，那么序列s（i）的個(gè)數(shù)是2i。周期翻倍，變成2i+1，若改變后序列線性復(fù)雜度為2i+1-2i=2i且WH（s（i+1））=2，那么s（i+1）的個(gè)數(shù)為2i。周期變?yōu)?j，（j＞i），序列s（j）的個(gè)數(shù)為（22）j-i-1×2i=22j-i-2。周期翻倍，變成2j+1，若改變后序列線性復(fù)雜度為2j+1-（2j+2i）且WH（s（j+1））=4的個(gè)數(shù)也是22j-i-2。

所以，滿足條件WH（e）=4，L（e）=L2（e）=2n-（2i+2j）的二元序列e的個(gè)數(shù)為22j-i-2×（24）n-j-1=24n-2j-i-6。

3）由上述可知，當(dāng)L（t）=0時(shí)，t+e的個(gè)數(shù)為24n-2j-i-6，（2）得證；當(dāng)L（t）＞0時(shí)，t+e的個(gè)數(shù)小于24n-2j-i-6×2L-1，因?yàn)榇藭r(shí)t+e的個(gè)數(shù)中存在重復(fù)的情況，即存在s+u，t+v∈TE，L4（s+u）=L4（t+v）=L，其中s≠t，u≠v，但s+u=t+v。排除重復(fù)序列的思想源自篩選法第二類的情況，需要檢查是否存在這樣的v，使得L（u+v）=L（s+t）＜L，以及這時(shí)v的個(gè)數(shù)。其中WH（u）=WH（v）=4，L（u）=L（v）=2n-（2i+2j）。下面考慮兩種情況。

①跟i，j，i0有關(guān)

定理6已得，L4（s（n））不存在形如，2n-2im，2n-（2j+2im），2n-（2i+2im）和部分2n-（2i1+2i2+2i3）的形式。這些值使得L4（s（n））取值不連續(xù)。

對于?u∈E，若2n-（2i+2k0+2j）＜L，i＜k0＜j，存在2j-k0-1個(gè)v，θ1=2j-k0；若2n-（2k1+2j）＜L，i＜k1＜j，存在2j-k1-1 個(gè)v，θ2=2j-k1；若2n-（2k2+2i+2j）＜L，0≤k2＜i，存在2i-k2-1個(gè)v，θ3=2i-k2。

若L同時(shí)滿足上述三種情況或其中兩種情況時(shí)，v的個(gè)數(shù)為θ1×θ2×θ3-1。

下面給出例子說明。

假設(shè)n=4，i=0，j=3時(shí)，設(shè)有序列u（5）=｛1100 0000 1100 0000｝，那么 滿足2n-（2i+2k0+2j）=3＜L，i＜k0＜j，k0=2 的v的總個(gè)數(shù)有1個(gè)，v=｛0000 1100 0000 1100｝；滿足2n-（2k+2j）=4＜L，k=2的v的總個(gè)數(shù)有3個(gè)。其中滿足2n-（2i+2k0+2j）=3＜L，k0=2的v個(gè)數(shù)2個(gè)；滿足2n-（2k1+2j）=4＜L，k1=2的v個(gè)數(shù)2個(gè)。所以v的個(gè)數(shù)共為2×2-1=3。

滿足2n-（2i+2k+2j）=5＜L，k=2的v的總個(gè)數(shù)有7個(gè)。其中滿足2n-（2k1+2j）=4＜L，k1=2的v個(gè)數(shù)2個(gè)；滿足2n-（2i+2k0+2j）=3＜L，k0=2的v個(gè)數(shù)4個(gè)。所以v的個(gè)數(shù)共為2×4-1=7。

②跟im＜ω＜n有關(guān)

對于 im＜ω＜n，存在15×（24）ω-im-1個(gè)序列 v，使得L（u+v）=2n-（2i+2j+2ω）＜L或 L（u+v）=2n-（2j+2ω）＜L或L（u+v）=2n-（2i+2ω）＜L或L（u+v）=2n-2ω＜L。

對于滿足任意條件的v有4個(gè)非零元素，若將v的周期加倍，那么一個(gè)原序列將會(huì)產(chǎn)生24個(gè)新序列。當(dāng)周期變?yōu)?n時(shí)，存在15+15×24+…+15×（24）n-im-2=（24）n-im-1-1個(gè)v，使得L（u+v）＜L。

下面用例子說明上面的結(jié)論。

假設(shè)n=4，i=0，j=1，設(shè)有序列u（4）=｛1111 0000 0000 0000｝。那么只存在v=｛0000 0000 1111 0000｝，使得L（u（4）+v）=2n-（2i+2j+2ω）=24-（20+21+23）=5。只存在v=｛0101 0000 1010 0000｝，v=｛1010 0000 0101 0000｝，使得L（u（4）+v）=L（u（4）+v）=2n-（2j+2ω）=24-（21+23）=6。只存在 v=｛0011 0000 1100 0000｝，v= ｛0110 0000 1001 0000｝，v=｛1001 0000 0110 0000｝，v=｛1100 0000 0011 0000｝，使得L（u（4）+v）=…= L（u（4）+v）=2n-（2i+2ω）=24-（20+23）=7。只存在v=｛0001 0000 1110 0000｝，…，v=｛1110 0000 0001 0000｝，使得L（u（4）+v）=…=L（u（4）+v）=2n-2ω=24-23=8。

由以上可知，當(dāng)j＜im＜n時(shí)

若2n-（2i+2j+2im）＞L，ε=0；若2n-（2i+2j+2im）＜L＜2n-（2j+2im），v的個(gè)數(shù)增加（24）n-im-1，ε=1；若2n-（2j+2im）＜L＜2n-（2i+2im），v的個(gè)數(shù)增加3×（24）n-im-1，ε=2；若2n-（2i+2im）＜L＜2n-2im，v的個(gè)數(shù)增加7×（24）n-im-1，ε=3。

綜上所述，滿足L（s（n））=L2（s（n））=2n-（2i+2j）＞L4（s（n））且L4（s（n））=L的2n周期二元序列s（n）的計(jì)數(shù)公式為

如果存在k0，使得2n-（2i+2k0+2j）＜L，i＜k0＜j，那么θ1=2j-k0；否則，θ1=1。

如果存在k1，使得2n-（2k1+2j）＜L，i＜k1＜j，那么θ2=2j-k1；否則，θ2=1。

如果存在k2，使得2n-（2k2+2i+2j）＜L，0≤k2＜i，那么θ3=2i-k2；否則，θ3=1。

由以上知，若L（s（n））=L2（s（n））＞L4（s（n）），當(dāng)已知L4（s（n））=L，而未知L（s（n））和L2（s（n））時(shí)，可以通過約束關(guān)系求得L（s（n））和L2（s（n）），進(jìn)而，求出二元序列s（n）的計(jì)數(shù)。

例2 若n=4，L（s（n））=L2（s（n））＞L4（s（n））=3，求滿足條件的二元序列s（n）的個(gè)數(shù)。由定理5知，L（s（n））的線性復(fù)雜度只能由一個(gè)2方體表示，并且｛i1，i2，i3｝不包括｛i，j｝。可以計(jì)算出L（s（n））的值為6，10或13。所以，當(dāng)L （s（n））=L2（s（n））＞L4（s（n））時(shí)，N4，4（3）=N4，4（6，6，3）+N4，4（10，10，3）+N4，4（13，13，3）=16+64+1 024=1 104。

2.4 4錯(cuò)線性復(fù)雜度的序列計(jì)數(shù)

由2.1，2.2，2.3小節(jié)可以得到

并且給出了計(jì)算N0，4（L），N2，4（L）和N4，4（L）的過程。那么，滿足L4（s（n））=L的序列s（n）的個(gè)數(shù)為

求解N4（L）過程，為算法1所示，例3為詳述過程：

算法1：求滿足4錯(cuò)線性復(fù)雜度二元序列計(jì)數(shù)

Input：4錯(cuò)線性復(fù)雜度L4（s），序列周期N

Output：二元序列計(jì)數(shù)N4

例3 若n=5，L4（s（n））=18，求滿足條件的以25為周期的二元序列s（n）的個(gè)數(shù)。

若L（s（n））=L2（s（n））=L4（s（n）），由定理1可得L（s（n））=18。進(jìn)而，N0，4（18）=N0，4（18，18，18）=131 072。

若L（s（n））＞L2（s（n））=L4（s（n）），由定理4可知L（s（n））的值可為24，28，30或31。

若L（s（n））＞L2（s（n））＞L4（s（n）），由引理8可知L（s（n）），L2（s（n））的值可為31，26；31，22；31，20；30，27；30，23或28，23。 進(jìn)而，N2，4（18）=N2，4（24，18，18）+N2，4（28，18，18）+N2，4（30，18，18）+N2，4（31，18，18）+N2，4（31，26，18）+N2，4（31，22，18）+N2，4（31，20，18）+N2，4（30，27，18）+N2，4（30，23，18）+N2，4（28，23，18）=191 889 408。

當(dāng)L（s（n））=L2（s（n））＞L4（s（n））時(shí)，由定理7可得L（s（n））的值為29，27，23。進(jìn)而，N4，4（18）=N4，4（29，29，18）+N4，4（27，27，18）+N4，4（23，23，18）=44 040 192。

所以，N4（18）=N0，4（18）+N2，4（18）+N4，4（18）=236 060 672。

3 結(jié)語

文中給出求滿足4錯(cuò)線性復(fù)雜度的2n周期序列計(jì)數(shù)的過程。通過將4錯(cuò)線性復(fù)雜度的研究分解為對關(guān)鍵錯(cuò)誤線性復(fù)雜度的研究，再使用方體理論和篩選法討論關(guān)鍵錯(cuò)誤線性復(fù)雜度，最后得到滿足4錯(cuò)線性復(fù)雜度序列的計(jì)數(shù)，并且用計(jì)算機(jī)編程得到的數(shù)據(jù)佐證了給出的求解過程的正確性。文中的研究方法可以推廣到求解其他k錯(cuò)線性復(fù)雜度序列計(jì)數(shù)。但是，隨著k值的增大，其求解過程將變得繁瑣。下一步，將研究簡便的方法來討論序列k錯(cuò)線性復(fù)雜度，力爭進(jìn)一步完善k錯(cuò)線性復(fù)雜度的研究。

［1］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.

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

［3］ETZION T，KOLOKOTRONIS N，LIMNIOTIS K，et al.Properties of the error linear complexity spectrum［J］.IEEE Trans on Inform Theory，2009，55 （10）：4681-4686.

［4］周建欽.具有2n線性復(fù)雜度的2n周期二元序列的3錯(cuò)線性復(fù)雜度［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2013，36（3）：399-413.

［5］MEDIDL W.On the stability of 2n-periodic binary sequence［J］.IEEE Trans on Information Theory，2005，51（3）：1151-1155.

［6］ZHOU Jianqin.On the k-error linear complexity for 2n-periodic binary sequences via Cube Theory［J］.Eprint Arxiv，2013，73（1）：55-75.

［7］周建欽，戴小平.具有穩(wěn)定k錯(cuò)線性復(fù)雜度的周期序列［J］.通信學(xué)報(bào)，2011，32（11A）：213-220.

［8］戴小平，畢松松，王喜鳳，等.k錯(cuò)線性復(fù)雜度具有第二下降點(diǎn)的 2n周期序列［EB/OL］.［2015-04-10］.http：//www.cnki.net/kcms/detail/ 31.1289.TP.20150410.1634.004.html.

［9］ZHOU J Q，LIU W Q.The k-error linear complexity distribution for 2n-periodic binary sequence［J］.Designs Codes and Cryptography，2014，73：55-75.

［10］ZHOU J Q，LIU W Q，WANG X F.Structure Analysis on the k-error Linear Complexity of 2n-periodic Binary Sequences［EB/OL］.［2014-08-09］.http：//arxiv.org/abs/1312.6927.

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

Counting functions for 2n-periodic binary sequences with 4-error linear complexity

BI Songsong，DAI Xiaoping
（School of Computer Science&Technology，Anhui University of Technology，Ma'anshan 243002，China）

The k-error linear complexity is one of the important measures for assessing the stability of sequence cipher.First，we presented the process of counting functions of 2n-periodic binary sequences with given 4-error linear complexity.Then we studied the critical error linear complexity via cube theory and sieve method.The possible values of the 4-error linear complexity of corresponding critical error point（descent point）were obtained and the number of sequences with given 4-error linear complexity of corresponding critical error point were established.Finally，we got the all the possible value forms of the 4-error linear complexity and the counting functions of 2n-periodic binary sequences.

critical error linear complexity；k-error linear complexity；cube theory；sieve method

TP918.1

A

1672-0687（2016）02-0055-09

2015-04-16

安徽省自然科學(xué)基金資助項(xiàng)目（1208085MF106）；安徽省教育廳自然科學(xué)基金資助項(xiàng)目（KY2013Z025）；安徽工業(yè)大學(xué)校青年科學(xué)基金資助項(xiàng)目（QZ201412）

畢松松（1990-），男，安徽鳳臺(tái)人，碩士研究生，研究方向：信息安全與密碼學(xué)。