周建欽，王傳銀

(杭州電子科技大學(xué)通信工程學(xué)院，浙江杭州310018)

0 引言

線性復(fù)雜度是衡量密鑰流序列隨機(jī)性的一個(gè)重要指標(biāo)，但高線性復(fù)雜度并不能保證序列是安全的。如果改變序列的一個(gè)周期段中一個(gè)或幾個(gè)元素，其線性復(fù)雜度發(fā)生很大的變化，則該序列仍然是密碼學(xué)意義上的弱序列。為了解決這個(gè)問題，文獻(xiàn)1引入了線性復(fù)雜度穩(wěn)定性度量指標(biāo):k-錯(cuò)線性復(fù)雜度。文獻(xiàn)2給出了2n-周期二元序列s的k-錯(cuò)線性復(fù)雜度嚴(yán)格小于線性復(fù)雜度L(s)的最小值:kmin=2WH(2n-L(s))，其中WH(b)表示整數(shù)b在二進(jìn)制表示下的Hamming重量。文獻(xiàn)3給出了線性復(fù)雜度為L的2n-周期二元序列的具體個(gè)數(shù)。文獻(xiàn)4給出了當(dāng)k=1，2時(shí)，線性復(fù)雜度為2n的2n周期二元序列的k-錯(cuò)線性復(fù)雜度分布情況。文獻(xiàn)5給出了2n周期二元序列的3錯(cuò)線性復(fù)雜度分布的完整計(jì)數(shù)公式。本文通過將5錯(cuò)線性復(fù)雜度的計(jì)算轉(zhuǎn)化為求Hamming重量最小的錯(cuò)誤序列，討論了線性復(fù)雜度為2n，周期為2n二元序列的5錯(cuò)線性復(fù)雜度分布情況，給出了5錯(cuò)線性復(fù)雜度為2n-3，2n-3+1和2n-3+2n-4的二元序列計(jì)數(shù)公式。

1 線性復(fù)雜度為2n二元序列的5錯(cuò)線性復(fù)雜度

定義1 設(shè)s(n)={s0，s1，s2，…，s2n-1}是二元序列s的第一周期，n≥1，根據(jù)Games-Chan算法，定義映射φn從到

引理1 定義1的映射φn滿足下面的性質(zhì)［4］:

(1)W(φn(s(n)))≤W(s(n));

(2)W(φn(s(n)))，W(s(n))奇偶性相同;

引理 2 設(shè) N(L)表示周期為 2n，線性復(fù)雜度為 L的二元序列個(gè)數(shù)［3］，則 N(L)

引理3 設(shè)s(n)，t(n)是2個(gè)不同的二元序列但線性復(fù)雜度均為c，1≤c〈2n-3，n〉3，u(n)，v(n)是2個(gè)不同的二元序列但線性復(fù)雜度均為2n，且u(n)，v(n)的非零元素個(gè)數(shù)分別為1，3或5，則u(n)+s(n)與t(n)+v(n)不同。

證明 欲證明u(n)+s(n)與t(n)+v(n)不同，即證明s(n)+u(n)+v(n)與t(n)不同，即證明u(n)+v(n)與s(n)+t(n)不同。

因?yàn)閟(n)，t(n)是2個(gè)不同的二元序列但線性復(fù)雜度均為c，1≤c〈2n-3，n〉3，所以s(n)+t(n)的線性復(fù)雜度小于2n-3，且s(n)+t(n)的2n個(gè)元素可以分成8個(gè)相同的部分。

假設(shè)u(n)+v(n)和s(n)+t(n)相同，則u(n)+v(n)的2n個(gè)元素可以分成8個(gè)相同的部分，故u(n)+v(n)的非零元素個(gè)數(shù)只能為8，u(n)+v(n)的線性復(fù)雜度為2n-3，與s(n)+t(n)的線性復(fù)雜度小于2n-3矛盾。

給出具有給定5錯(cuò)線性復(fù)雜度的2n周期二元序列個(gè)數(shù)的具體表達(dá)式:

定理1 設(shè)N5(2n-3)表示周期為2n，線性復(fù)雜度為L(s)=2n，5錯(cuò)線性復(fù)雜度為2n-3的二元序列s的個(gè)數(shù)，n〉3，則 N5(2n-3

證明 設(shè)序列s(n)是線性復(fù)雜度為2n-3的二元序列，則由引理2知s(n)的個(gè)數(shù)為n=5。

設(shè)二元序列u(n)的線性復(fù)雜度為2n且W(u(n))=1，可知u(n)+v(n)的5錯(cuò)線性復(fù)雜度為2n-3。

設(shè)序列u(n)的線性復(fù)雜度為2n且W(u(n))=3，且u(n)中任意兩個(gè)非零元素距離為2n-3的倍數(shù)，易知恰好存在一個(gè)序列v(n)且W(v(n))=5，使得u(n)+v(n)的線性復(fù)雜度為2n-3，即u(n)+s(n)的5錯(cuò)線性復(fù)雜度小于2n-3。

設(shè)序列u(n)的線性復(fù)雜度為2n且W(u(n))=5，且u(n)中至少4個(gè)非零元素距離為2n-3的倍數(shù)，易知恰好存在一個(gè)序列 v(n)，使得 u(n)+v(n)的線性復(fù)雜度為2n-3，即u(n)+s(n)的5錯(cuò)線性復(fù)雜度小于2n-3。

設(shè)序列u(n)的線性復(fù)雜度為2n且W(u(n))=3，則u(n)的個(gè)數(shù)為

設(shè)序列u(n)的線性復(fù)雜度為2n，W(u(n))=3，且u(n)中任意兩個(gè)非零元素距離為2n-3的倍數(shù)，則u(n)的個(gè)數(shù)為

設(shè)序列u(n)的線性復(fù)雜度為2n且W(u(n))=5，則u(n)的個(gè)數(shù)為

設(shè)序列u(n)的線性復(fù)雜度為2n，W(u(n))=5，且u(n)中恰好4個(gè)非零元素距離為2n-3的倍數(shù)，則u(n)的個(gè)數(shù)為

設(shè)序列u(n)的線性復(fù)雜度為2n，W(u(n))=5，且u(n)中任意5個(gè)非零元素距離為2n-3的倍數(shù)，則u(n)的個(gè)數(shù)為

故5錯(cuò)線性復(fù)雜度為2n-3的二元序列s的個(gè)數(shù)為

例如，當(dāng)n=4時(shí)，N5(24-3)=7 200，即線性復(fù)雜度L(s)=24，5錯(cuò)線性復(fù)雜度為2的二元序列s的個(gè)數(shù)為7 200，通過計(jì)算機(jī)驗(yàn)證可得同樣的結(jié)果。

定理2 設(shè)N5(2 +1)表示周期為2，線性復(fù)雜度為L(s)=2，5錯(cuò)線性復(fù)雜度為2 +1的二元序列s的個(gè)數(shù)，n〉4，則

與定理1證明方法類似，只需考慮更復(fù)雜的重復(fù)情況即可。

定理3 設(shè)N5(2n-2-2n-4)表示周期為2n，線性復(fù)雜度為L(s)=2n，5錯(cuò)線性復(fù)雜度為2n-2-2n-4的二元序列s的個(gè)數(shù)，n〉3，則

與定理1、2證明方法類似，只需考慮更復(fù)雜的重復(fù)情況即可。

2 結(jié)束語

通過研究周期為2n的二元序列線性復(fù)雜度，將具體5錯(cuò)線性復(fù)雜度值所對(duì)應(yīng)的原序列的計(jì)數(shù)轉(zhuǎn)化為求Hamming重量最小的錯(cuò)誤序列的個(gè)數(shù)?；贕ames-Chan算法，本文討論了線性復(fù)雜度為2n的2n周期二元序列的5錯(cuò)線性復(fù)雜度分布情況，給出了若干具體5錯(cuò)線性復(fù)雜度對(duì)應(yīng)原序列個(gè)數(shù)的計(jì)算公式?；谏厦娴挠懻摚瑢?duì)隨機(jī)周期序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的統(tǒng)計(jì)性質(zhì)［6］，也可研究線性復(fù)雜度為2n的2n周期二元序列的5錯(cuò)線性復(fù)雜度對(duì)應(yīng)原序列個(gè)數(shù)的期望值。

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

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

［3］ Rueppel R A.Analysis and Design of Stream Ciphers［M］.Berlin:Springer-Verlag，1986:20-152.

［4］ MeidlW.On the stablity of 2n-periodic binary sequences［J］.IEEE Transactions on Information Theory，2005，51(3):1 151-1 155.

［5］ Zhou J.A counterexample concerning the 3-error linear complexity of 2n-periodic binary sequences［EB/OL］.http://www.springerlink.com/content/7 562p69 561 624 154/，2011-05-02.

［6］ 蘇明.周期序列復(fù)雜度的分布［D］.天津:南開大學(xué)，2004.