2n-周期二元序列的5-錯線性復雜度

周建欽，王洪翠

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

2n-周期二元序列的5-錯線性復雜度

周建欽1，2，王洪翠1

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

密鑰流序列的隨機性檢測和穩定性度量的兩項重要指標：線性復雜度與k-錯線性復雜度，對密鑰流序列密碼強度的研究具有極其重要的意義。分析討論漢明重量最小的錯誤序列是計算給定k-錯線性復雜度條件下所對應的原序列個數的一個有效方法。使用該方法，分別給出了5-錯線性復雜度等于2n-3+x，2n-2-2n-m以及2n-1-2n-3時，周期和線性復雜度均等于2n的原序列s（n）的計數公式，并通過計算機編程進行了驗證。

密鑰流序列；線性復雜度；k-錯線性復雜度；k-錯線性復雜度分布

線性復雜度與k-錯線性復雜度分別用來度量密鑰流序列的隨機性和穩定性。為了避免攻擊者通過B-M算法[1]得到整個序列，密鑰流序列的線性復雜度應該盡量大。1983年，國外學者Games和Chan提出了2n-周期二元序列線性復雜度的快速算法[2]。然而，現實的通信過程中是存在干擾的，當密鑰流序列被改變少量比特時，其線性復雜度可能急劇下降。例如，24-周期二元序列s（4）=｛1000 0000 0000 0000｝，其線性復雜度為16，改變s（4）的一個比特，得到全零序列后，其線性復雜度降為0。我國學者丁存生，肖國鎮和單煒娟[3]最早關注這個問題，隨后國外學者Stamp與Martin[4]引入k-錯線性復雜度的概念作為度量序列穩定性的一個指標。國內學者蘇明通過對F2上2n-周期序列線性復雜度與1-錯線性復雜度的研究，發現在一定條件下，不同序列具有固定的1-錯線性復雜度[5]。隨后，Meidl給出了線性復雜度為2n的2n-周期二元序列的k-錯線性復雜度分布[6]，k=1，2。

為了計算給定k-錯線性復雜度條件下原序列的個數，先求線性復雜度等于給定的k-錯線性復雜度的二元序列p（n）的個數和漢明重量不大于k的可能成為錯誤序列的u（n）的個數。之后，基于組合數學的篩選法，排除不滿足條件的序列u（n），從而給出5-錯線性復雜度等于2n-3+x，2n-2-2n-m和2n-1-2n-3時，周期和線性復雜度均等于2n的原序列s（n）的計數公式。

1 預備知識

定義1[7]設在GF（q）上，N-周期序列s=（s0，s1，…，sN-1）N，其k-錯線性復雜度LCk（s）定義為

其中，e=（e0，e1，…，eN-1）N，WH（e）表示序列e在一個周期內的漢明重量。

引理1[8]設周期為2n的二元序列，如果，則有；如果，則有。

引理2[9]設周期為2n的二元序列s（n），若s（n）的一個周期內的漢明重量為奇數，則LC（s（n））=2n；若s（n）的一個周期內的漢明重量為偶數，則LC（s（n））＜2n。

引理3[10]設Ei表示周期為2n的二元序列，且序列一個周期內只有第i位上的元素是1，其他元素全為0，0≤i＜2n。如果j-i=2r（1+2a），a≥0，0≤i＜j＜2n，r≥0則LC（Ei+Ej）=2n-2r。

引理4[11]設s（n）為2n-周期二元序列，其線性復雜度為L，N（L）表示滿足以上條件的序列s（n）的個數，則

引理5i）設2n-周期二元序列p（n），LC（p（n））=c，1≤c＜2n-1-3，且c≠2n-1-2d1，2≤d1≤n-2，c≠2n-1-2d1-2d2，0≤d2＜d1≤n-2。若u（n）也是2n-周期序列，WH（u（n））=1，3或5，則LC5（p（n）+u（n））=c。

ii）設2n-周期二元序列p（n），LC（p（n））=c，c=2n-1-2d1，0≤d1≤n-2，或c=2n-1-2d1-2d2，0≤d2＜d1≤n-2。則存在序列u（n），WH（u（n））=1，3或5，使得LC5（p（n）+u（n））＜c。

證明求p（n）+u（n）的5-錯線性復雜度，就是在p（n）+u（n）上疊加漢明重量為1，3或5的序列，然后求其最小線性復雜度。

i）設不同于u（n）的序列v（n），WH（v（n））=1，3或5。

若LC（u（n）+v（n））≥2n-1，則LC（p（n）+u（n）+v（n））≥2n-1。由LC（p（n）+u（n）+v（n））=c，1≤c＜2n-1-3，故LC5（p（n）+u（n））=c。

若LC（u（n）+v（n））＜2n-1，則有Left（u（n）+v（n））=Right（u（n）+v（n）），此時WH（Left（u（n）+v（n）））=2或4，LC（u（n）+v（n））=LC（Left（u（n）+v（n）））=2n-1-2d1，0≤d1≤n-2或2n-1-2d1-2d2，0≤d2＜d1≤n-2，因此，LC（p（n）+u（n）+v（n））= max［LC（p（n）），LC（u（n）+v（n））］。

綜上，LC（p（n）+u（n）+v（n））≥LC（p（n）），故LC5（p（n）+u（n））=min［LC（p（n）+u（n）+v（n））］=c。

ii）設序列p（n），LC（p（n））=c，c=2n-1-2d1，0≤d1≤n-2，或c=2n-1-2d1-2d2，0≤d2＜d1≤n-2，則存在序列u（n），WH（u（n））=1，3或5和序列v（n），WH（v（n））=1，3或5，使得LC（u（n）+v（n））=c，即LC5（p（n）+u（n））＜c。

證畢。

2 5-錯線性復雜度的原序列計數公式

引理6設s（n）為2n-周期二元序列，N5（2n-3+x）表示線性復雜度等于2n，5-錯線性復雜度等于2n-3+x的序列s（n）的個數，n≥5，1≤x＜2n-4，則

證明設序列s（n）=p（n）+u（n），其中LC（p（n））=2n-3+x，1≤x＜2n-4，WH（u（n））=1，3或5，則u（n）有個。

下面分兩種情況加以討論，一種是LC5（p（n）+u（n））＜2n-3+x，另外一種是存在不同于p（n）的序列q（n），使得p（n）+u（n）=q（n）+v（n），此時有s（n）=p（n）+u（n）=q（n）+v（n），也就是說s（n）多加了一倍。

現假設w（n）=u（n）+v（n），WH（u（n））=1，3或5，WH（v（n））=1，3或5，并且LC（w（n））≤2n-3+x，1≤x＜2n-4。這樣LC（w（n））≤2n-3+x＜2n-2，因此，WH（w（n））=8并且呈4等分分布，即有LC（w（n））=2n-2-2n-m，3≤m≤n。

當m=3時，有LC（w（n））=2n-3＜2n-3+x；當m＞3時，有LC（w（n））=2n-2-2n-m≥2n-2-2n-4=2n-3+2n-4＞2n-3+x。因此，m只能為3。

故LC（u（n）+v（n））只能取2n-3，這樣LC5（p（n）+u（n））＜2n-3+x的情況就不存在，只需討論p（n）+u（n）=q（n）+v（n）的情況即可，具體情況如下：

（1）當WH（u（n））=3時，有唯一的序列v（n），WH（v（n））=5，使得LC（u（n）+v（n））=2n-3，這樣的u（n）有個。（2）當WH（u（n））=5，且5個非零比特均屬于w（n）時，有唯一的序列v（n），WH（v（n））=3，使得LC（u（n）+v（n））=2n-3，這樣的u（n）有個。（3）當WH（u（n））=5，且只有4個非零比特屬于w（n）時，也只有唯一的序列v（n），WH（v（n））=5，使得LC（u（n）+v（n））=2n-3，這樣的u（n）有個。

根據引理4，滿足LC（p（n）=2n-3+x的序列p（n）的個數為：。

綜上，滿足LC5（s（n））=2n-3+x的非平衡二元序列s（n）的個數為

證畢。

例如：當n=5，x=1，LC5（s（n））=5時，N5（5）=3 244 544，與計算機編程驗證結果一致。

引理7設s（n）為2n-周期二元序列，N5（2n-2-2n-m）表示線性復雜度等于2n，5-錯線性復雜度等于2n-2-2n-m的序列s（n）的個數，n≥4，4≤m≤n，則

其中，B1，B2，B3，B4，B5，B6，B7定義見證明過程。

證明設序列s（n）=p（n）+u（n），其中LC（p（n））=2n-2-2n-m，n≥4，4≤m≤n，WH（u（n））=1，3或5，則u（n）的個數為：個。

（1）根據引理5可知，存在不同于u（n）的序列v（n），WH（v（n））=3或5，使得LC（u（n）+v（n））=2n-2-2n-m，即LC5（s（n））=LC5（p（n）+u（n））=min[LC（p（n）+u（n）+v（n））]＜2n-2-2n-m。

設序列w（n）=u（n）+v（n），滿足LC（w（n））=2n-2-2n-m，WH（w（n））=8，則w（n）的每個周期可以等分成長度為2n-2的四部分，且每部分恰有2個非零比特，其距離為2n-m的奇數倍。這樣的w（n）有個。其中每個w（n）均與另外的個w（n）有4個非零比特的交集。這樣的4個非零比特組合構成了集合P1={ai，ai+2n-2，ai+2n-1，ai+3·2n-2|0≤i＜2n-2}，易知集合P1的元素個數為2n-2。

①當WH（u（n））=3，WH（v（n））=5時，u（n）中的3個非零比特均屬于w（n）中的8個非零比特。若這3個非零比特從屬于P1中的組合，則這樣的u（n）的個數為。若這3個非零比特不從屬于P1中的組合，則這樣的u（n）的個數為。因此，滿足條件的u（n）總共有個。

②當WH（u（n））=5，WH（v（n））=3時，u（n）中的5個非零比特均屬于w（n）中的8個非零比特，這樣的u（n）有個。

③當WH（u（n））=5，WH（v（n））=5時，u（n）中的4個非零比特屬于w（n）的8個非零比特。

（a）若這4個非零比特a1，a2，a3，a4屬于集合P1，那么u（n）中的第5個非零比特a5與a1，a2，a3，a4的距離不能為2n-m的奇數倍，否則就與②中的情況重復，即u（n）中的5個非零比特均屬于w（n）的8個非零比特。距a1，a2，a3，a4為2n-m奇數倍的位置有個，再減去a1，a2，a3，a4本身的4個位置，即a5只能位于剩下的2n-2m-1-4個位置。這樣的u（n）有個。

（b）若這4個非零比特a1，a2，a3，a4不屬于集合P1，這樣的u（n）有個。然而，當4個非零比特中的a1，a2，a3從屬于P1中的組合，a4，a5與a1，a2，a3間的距離為2n-m的奇數倍且a4，a5不從屬于P1中的組合時，可從兩個不同的w（n）中分離得到相同的u（n），即得到的u（n）是雙倍的。a4，a5的位置有種選擇，即這樣的u（n）的個數為。

例如：由計算機編程可得，當w（n）為{1100 0000 1100 0000 1100 0000 1100 0000}時，u（n）可以為{1101 0000 1000 0000 1000 0000 0000 0000}；當w（n）為{1001 0000 10010000 10010000 1001 0000}時，u（n）同樣可以為{1101 0000 1000 0000 1000 0000 0000 0000}。

因此，當WH（u（n））=5，WH（v（n））=5時，滿足條件的u（n）有個。

（2）假設LC（w（n））=LC（u（n）+v（n））=2n-2-2n-k＜2n-2-2n-m，3≤k≤m-1，此時存在序列q（n）=p（n）+u（n）+v（n），使得LC（q（n））=LC（p（n）+u（n）+v（n））=2n-2-2n-m，即存在s（n）=q（n）+v（n）=p（n）+u（n），這樣的w（n）總共有2n+k-6個。所有這樣的序列w（n）構成集合P2，則集合P2的元素個數為2n+k-6。

④當WH（u（n））=3，WH（v（n））=5，并且u（n）中的3個非零比特均屬于P2中的w（n）而不從屬于P1中的組合時，這樣的u（n）有個。此時，存在一個不同于u（n）的v（n），使得LC（u（n）+v（n））＜2n-2-2n-m。

⑤當WH（u（n））=5，WH（v（n））=3時，u（n）中的5個非零比特均屬于P2中的w（n），并且當4個非零比特a1，a2，a3，a4屬于集合P1，a5與a1，a2，a3，a4相距2n-k的奇數倍，即為2n-m的偶數倍時，u（n）與（a）的情況是重復的。這里u（n）對應的v（n）即為情況④,所以u（n）的個數為B5=B4，此時存在一個不同于u（n）的v（n），使得LC（u（n）+v（n））＜2n-2-2n-m。

⑥當WH（u（n））=5，WH（v（n））=5時，u（n））中的4個非零比特屬于P2中的w（n）且不屬于集合P1，否則會與②、（a）中的情況重復，這樣的u（n）有個。

（c）假設u（n）中的3個非零比特a1，a2，a3從屬于P1中的組合。

i）當a4與a1，a2，a3相距2n-k的奇數倍，a5與a1，a2，a3相距2n-m的奇數倍時，這里的u（n）與（b）中的u（n）是重復的，這樣的u（n）有個。

ii）當a4與a1，a2，a3相距2n-k的奇數倍，a5與a1，a2，a3相距2n-j（k＜j＜m）的奇數倍時，有兩個不同的v（n），使得LC（u（n）+v（n））＜2n-2-2n-m；同樣，當a4，a5與a1，a2，a3相距均為2n-k（4≤k＜m）的奇數倍且a4，a5不從屬于P1中的組合時，也有兩個不同的v（n），使得LC（u（n）+v（n））＜2n-2-2n-m，這些情況要特殊考慮，這樣的u（n）有個。而此時可從兩個不同的w（n）中分離得到相同的u（n），即要減去雙倍的u（n）的個數。

因此，滿足以上條件的u（n）總共有個。此時，存在一個不同于u（n）的v（n），使得LC（u（n）+v（n））＜2n-2-2n-m。

（d）現在，來考慮（c）中的特殊情況ii）。當a4，a5與a1，a2，a3相距均為2n-k（4≤k＜m）的奇數倍且a4，a5不從屬于P1中的組合時，存在不同于u（n）的序列v1（n），v2（n），v1（n）≠v2（n）且wH（v1（n））=wH（v2（n））=5，使得LC（u（n）+v1（n））=LC（u（n）+v2（n））=2n-2-2n-k＜2n-2-2n-m。當a4與a1，a2，a3相距2n-k的奇數倍，a5與a1，a2，a3相距2n-j（k＜j＜m）的奇數倍時，也存在不同于u（n）的序列v1（n），v2（n），v1（n）≠v2（n）且wH（v1（n））=wH（v2（n））=5，使得LC（u（n）+v1（n））=2n-2-2n-k＜2n-2-2n-m，LC（u（n）+v2（n））=2n-2-2n-j＜2n-2-2n-m。此時有q1（n）=p（n）+u（n）+v1（n），q2（n）=p（n）+u（n）+v2（n），LC（q1（n））=LC（q2（n））=2n-2-2n-m，即存在s（n）=p（n）+u（n）=q1（n）+v1（n）=q2（n）+v2（n）。此時的s（n）多加了兩倍，因此，要減去u（n），v1（n），v2（n）總數的2/3。

下面考慮一種特殊情況。設n=6，m=6，則k可取3，4，5，將從屬于P1中組合的3個非零比特a1，a2，a3視為基準點。設a4，a5與基準點相距均為2n-5=2的奇數倍且a4，a5不從屬于P1中組合的u（n）構成集合Q1；a4與基準點相距2n-5=2的奇數倍，a5與基準點相距2n-3=8的u（n）構成集合Q2；a4與基準點相距2n-5=2的奇數倍，a5與基準點相距2n-4=4的奇數倍的u（n）構成集合Q3。

i）對于Q1中的u（n），當a4距基準點的距離為d1，a5距基準點的距離為d2時，存在不同于u（n）的序列v1′（n），v2′（n），使得s（n）=p（n）+u（n）=q1′（n）+v1′（n）=q2′（n）+v2′（n）。若d1，d2差值為4的奇數倍，則在v1′（n），v2′（n）中，a4′距新的基準點的距離均為4的奇數倍，a5′距新的基準點的距離均為2的奇數倍，即v1′（n）∈Q3，v2′（n）∈Q3。

若d1，d2差值為8，則在v1′（n），v2′（n）中，a4′距新的基準點的距離均為8，a5′距新的基準點的距離均為2的奇數倍，即v1′（n）∈Q2，v2′（n）∈Q2。

ii）對于Q2中的u（n），存在不同于u（n）的序列v1″（n），v2″（n），使得s（n）=p（n）+u（n）=q1″（n）+v1″（n）=q2″（n）+v2″（n）。在v1″（n）中，a4″，a5″距新的基準點的距離均為2的奇數倍；在v2″（n）中，a4″距新的基準點的距離為2的奇數倍，a5″距新的基準點的距離為8，此時v1″（n）∈Q1，v2″（n）∈Q2。

iii）對于Q3中的u（n），存在不同于u（n）的序列v1?（n），v2?（n），使得s（n）=p（n）+u（n）=q1?（n）+v1?（n）=q2?（n）+v2?（n）。在v1?（n）中，a4?，a5?距新的基準點的距離均為2的奇數倍；在v2?（n）中，a4?距新的基準點的距離為2的奇數倍，a5?距新的基準點的距離為4的奇數倍，此時v1?（n）∈Q1，v2?（n）∈Q3。

綜上可得，v1′（n），v2′（n），v1″（n），v2″（n），v1?（n），v2?（n）均包含在集合Q1，Q2，Q3中。一般性的情況均可類似證明。

滿足（c）中的特殊情況ii）的u（n）個數為。

根據引理4，滿足LC（p（n））=2n-2-2n-m的序列p（n）總共有個。

綜上所述，滿足LC5（s（n））=2n-2-2n-m的非平衡周期二元序列s（n）的個數為

證畢。

例如：當n=5，m=5，LC5（s（n））=7時，N5（7）=11 184 128，與計算機編程檢驗結果一致。

引理8設s（n）為2n-周期二元序列，N5（2n-1-2n-3）表示線性復雜度等于2n，5-錯線性復雜度等于2n-1-2n-3的序列s（n）的個數，n≥5，則

其中，C1，C2，C3，C4，C5定義見證明。

證明設s（n）=p（n）+u（n）序列，其中LC（p（n））=2n-1-2n-3，WH（u（n））=1，3或5，則u（n）有個。

（1）當WH（u（n））=1或3時，總存在序列v（n），WH（v（n））=3或5，使得LC（u（n）+v（n））=2n-1-2n-3，此時有LC5（s（n））= min[LC（p（n）+u（n）+v（n））]＜2n-1-2n-3。

（2）當WH（u（n））=5時，將u（n）分成2n-3個子序列，每個子序列中各個比特位置如下

①當u（n）中至少有3個非零比特屬于同一子序列時，肯定存在序列v（n），WH（v（n））=1，3或5，使LC（u（n）+v（n））=2n-1-2n-3，即LC5（s（n））=min[LC（p（n）+u（n）+v（n））]＜2n-1-2n-3。

當u（n）中的5個非零比特位于同一序列時，這樣的u（n）有個；當4個非零比特位于同一子序列時，這樣的u（n）有個；當3個非零比特a1，a2，a3位于同一子序列，另外兩個非零比特a4，a5位于另外的一個子序列時，這樣的u（n）有個；當a1，a2，a3位于同一子序列，而a4，a5另屬于兩個不同的子序列時，這樣的u（n）有個。因此，有個u（n），使得LC5（s（n））=min[LC（p（n）+u（n）+v（n））]＜2n-1-2n-3。

②當u（n）中非零比特a1，a2位于同一子序列，a3，a4也位于同一子序列時，u（n）的個數為

當a1，a2與a3，a4這兩對非零比特間的距離為2n-3的偶數倍時，這樣的u（n）有個。其中，至少有一對非零比特的距離為2n-1的u（n）個數為，因此，

這時，存在3個不同于u（n）的v（n），WH（v（n））=5，使得LC（u（n）+v（n））＜2n-1-2n-3，即存在序列q（n）=p（n）+u（n）+v（n），LC（q（n））=2n-1-2n-3，也就是s（n）=q（n）+v（n）=p（n）+u（n）。

對于其余的C2-C3個u（n），均存在v（n），使得LC5（s（n））=min[LC（p（n）+u（n）+v（n））]＜2n-1-2n-3。

③當a1，a2位于同一子序列，a3，a4而位于另外兩個不同的子序列時，這樣的u（n）個數為

然而，當a1，a2相距為2n-3的偶數倍時，這樣的u（n）有個，其中a1，a2相距為2n-1的情況有個。a1，a2相距為2n-3的偶數倍且不為2n-1的u（n）個數,這時，存在1個不同于u（n）的v（n），WH（v（n））=5，使得LC（u（n）+v（n））＜2n-1-2n-3。

對于其余的C4-C5個u（n），均存在v（n），使得LC5（s（n））=min[LC（p（n）+u（n）+v（n））]＜2n-1-2n-3。

根據引理4，使得LC（p（n））=2n-1-2n-3的序列p（n）有22n-1-2n-3-1個。

綜上所述，滿足LC5（s（n））=2n-1-2n-3的非平衡周期二元序列s（n）的個數為

證畢。

例如：當n=5，LC5（s（n））=12時，N5（12）=19 922 944，與計算機編程檢驗結果一致。

基于Games-Chan算法，通過分析5-錯線性復雜度已給定的序列的錯誤序列，利用組合排列的相關方法進行篩選，給出了5-錯線性復雜度等于2n-3+x，2n-2-2n-m以及2n-1-2n-3時,周期和線性復雜度均等于2n的原序列s（n）的計數公式，并通過計算機編程給予驗證。

[1]Berlekamp S R.Algebraic Coding Theory[M].New York：Mcgraw-Hill，1968.

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

[3]Ding C，Xiao G，Shan W.The Stability Theory of Stream Ciphers[M].Berlin：Springer-Verlag，1991：85-88.

[4]Stamp M，Martin C F.An algorithm for thek-error linear complexity of binary sequences with period 2n[J].IEEE Transactions on Information Theory，1993，39（4）：1398-1401.

[5]蘇明.周期序列復雜度的分布[D]．天津：南開大學，2004．

[6]Meidl W.On the stability of 2n-periodic binary sequences[J].IEEE Transactions on Information Theory，2005，51（3）：1151-1155．

[7]李鶴齡，戚文峰.Fp上Pn-周期序列的k-錯誤序列[J].通信學報，2010，31（6）：19-24.

[8]周建欽，劉軍.2n-周期二元序列的3-錯誤序列分布[J].電子與信息學報，2012，34（8）：1923-1927.

[9]唐淼.2n-周期序列的k-錯線性復雜度期望的界[J].巢湖學院學報，2011，13（3）：1-4.

[10]周建欽.具有2n線性復雜度的2n周期二元序列的3錯線性復雜度[J].應用數學學報，2013，36（3）：399-413.

[11]周建欽,陳加如.2n-周期平衡二元序列的6-錯線性復雜度[J].杭州電子科技大學學報，2011，31（6）：17-19.

The 5-error linear complexity of 2n-periodic unbalanced binary sequences

ZHOU Jianqin1，2，WANG Hongcui1
（1.Telecommunication School，Hangzhou Dianzi University，Hangzhou 310018，China；2.School of Computer Science&Technology，Anhui University of Technology，Ma'anshan 243032，China）

The linear complexity andk-error linear complexity have been used to measure randomness and stability of keystream sequences.They are extremely important for studying keystream strength.Studying error sequences with minimal Hamming weight is an effective method for calculating the number of sequences with the givenk-error linear complexity.Based on this method,counting functions ofs（n）with both period and linear complexity equal to 2nand 5-error linear complexity equal to 2n-3+x，2n-2-2n-mand 2n-1-2n-3are derived respectively. They are also verified by computer program.

keystream sequences；linear complexity；k-error linear complexity；k-error linear complexity distribution

TN918.1

A

1672-0687（2015）01-0001-07

責任編輯：艾淑艷

2013-09-25

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

周建欽（1963-），男，山東巨野人，教授，碩士，研究方向：通信，密碼學與理論計算機科學。