2n-周期序列的k錯線性復(fù)雜度期望的界

唐淼

（安徽農(nóng)業(yè)大學(xué)理學(xué)院，安徽 合肥 230036）

2n-周期序列的k錯線性復(fù)雜度期望的界

唐淼

（安徽農(nóng)業(yè)大學(xué)理學(xué)院，安徽 合肥 230036）

對于有限域F2上的滿線性復(fù)雜度的2n-周期序列和奇數(shù)k≥3，通過對k錯線性復(fù)雜度的取值范圍和相應(yīng)的序列個數(shù)的分析，得到其k錯線性復(fù)雜度期望的上界和下界。

線性復(fù)雜度；k錯線性復(fù)雜度；周期序列；界

1 引言

線性復(fù)雜度和k錯線性復(fù)雜度是序列密碼中的兩個重要密碼強(qiáng)度指標(biāo)，密鑰序列必須具有較高的線性復(fù)雜度和k錯線性復(fù)雜度.對于有限域F2上的2n-周期序列，Rueppel[1]給出了與各個線性復(fù)雜度值對應(yīng)的序列個數(shù)以及這類序列的線性復(fù)雜度期望，文獻(xiàn)[2，3]分別給出了能夠快速計算線性復(fù)雜度和k錯線性復(fù)雜度的算法，而文獻(xiàn)[4]給出了k錯線性復(fù)雜度小于線性復(fù)雜度的最小的 值的表達(dá)式.文獻(xiàn)[5－8]對各種周期序列的錯線性復(fù)雜度值的分布進(jìn)行了研究，得出了一些周期序列的k錯線性復(fù)雜度期望的精確值或界.

2 預(yù)備知識

設(shè) s（n）=（s0，s1，…，s2n-1）是有限域 F2上的2n維向量，s=（s0，s1，…，s2n-1）表示以 s（n）為周期的2n-周期序列.S的線性復(fù)雜度是指能夠生成S的最短的線性反饋移位寄存器的級數(shù)，記為LC（S），0序列的線性復(fù)雜度定義為0.S的k錯線性復(fù)雜度是指在s（n）中改變不超過k個分量所能得到的周期序列線性復(fù)雜度的最小值，記為 LCk（S），即

其中 W（e（n））指向量 e（n）的漢明重量，即 的不等于 0 的分量的個數(shù).

引理 1[1]域 F2上的2n-周期序列中，線性復(fù)雜度等于 l的個數(shù)為 N（0）=1(l=0 時)，N（l）=2l-1(1≤l≤2n時).

引理2[4]設(shè)S是域F2上的2n-周期序列，則

1） LC（S）=2n當(dāng)且僅當(dāng)W（s（n））為奇數(shù)；

2） LCk（S）=LCk+1（S），k 為奇數(shù)；

3） LCk（S）≠2n-2t，其中 k≥2，0≤t≤n-1.

由引理1可知域F2上的2n-周期序列共有22n個，而其中線性復(fù)雜度等于2n的序列（即滿線性復(fù)雜度的序列）共有22n-1個,包含了整個序列一半的數(shù)量.又由引理2可知LCk（S）=LCk+1（S），k為奇數(shù)，故只需討論k為奇數(shù)時的情形即可得到所有k的情形.

在文獻(xiàn)[2]中，Games和Chan給出了能夠快速計算2n-周期序列S的線性復(fù)雜度的算法，下面簡單的描述 Chan-Games 算法.將 s（n）=（s0，s1，…，s2n-1）分為等長的兩部分 L（S（n））=（s0，s1，…，s2n-1-1）和 R（s（n））=（s2n-1，s2n-1+1，…，s2n-1）.

1）若 L（s（n））=R（s（n）），則 LC（S）=LC（L（s（n）∞）;

2）若 L（s（n））≠R（s（n）），則 LC（S）=2n-1+LC（（L（s（n）+R（s（n）））∞）.

以遞歸的方式繼續(xù)這個過程可以得到S的線性復(fù)雜度.可以看出，在每一輪遞歸中線性復(fù)雜度只有當(dāng)L≠R（1≤i≤n）時才會增加，且當(dāng)L=R時，2i-2將不會加到線性復(fù)雜度上，而在后面的遞歸過程中線性復(fù)雜度最多再增加2i-2+…+20+1=2i-1.

即 S（n-1）=φn（S（n））=L（s（n））+R（s（n）），φn具有如下性質(zhì)：

P1：W（φn（S（n）））≤W（S（n））且同時為奇數(shù)或者同時為偶數(shù)；

P2：S（n）原象的集合共包含 22n個元素.

3 錯線性復(fù)雜度期望的界

引理3若3≤k≤2n-1且k為奇數(shù)，則對域F2上滿線性復(fù)雜度的2n周期序列，k錯線性復(fù)雜度屬于（2n-2t+1，2n-2t），1≤t≤n-1，的序列個數(shù)為

證明F2對域 上滿線性復(fù)雜度的2n周期序列S，由引理2可知其k錯線性復(fù)雜度可能的值或者屬于（2n-2t+1，2n-2t），1≤t≤n-1，或者等于 0. 而計算 k 錯線性復(fù)雜度的 Stamp-Matin[3]算法是在 Chan-Games[2]算法的基礎(chǔ)上，給定最多k個差錯值，盡量在算法的越早的循環(huán)中允許差錯發(fā)生使得L=R，從而盡可能的減小算法最后得到的線性復(fù)雜度.

因此，k 錯線性復(fù)雜度 LCk（S）∈（2n-2t+1，2n-2t）當(dāng)且僅當(dāng) W（s（t+1））＞k 且 W（s（t））≤k. 滿足 W（s（t））≤k的 s（t）共有個，其中 j只取奇數(shù)，而對于每一個 s（t），由于 s（t）=φt+1…φn（s（n）），由 φn性質(zhì)可知對應(yīng)的向量 s（n）共有 22n-122n-2…22t=22n-2t個，即滿足 W（s（t））≤k 的序列個數(shù)為同理可得，滿足 W（s（t+1））≤k 的的序列個數(shù)為由引理 2 及 φn性質(zhì)可知 W（s（t））≤W（s（t+1））≤…≤W（s（n））且同奇偶，又由引理 1 可知 W（s（n））必為奇數(shù)，故 W（s（t）），1≤t≤n，均為奇數(shù).顯然，滿足 W（s（t+1））≤k 的的序列全部滿足 ，故 W（s（t））≤k 錯線性復(fù)雜度屬于（2n-2t+1，2n-2t），的序列個數(shù)為

4 結(jié)束語

本文僅對有限域F2上滿線性復(fù)雜度的2n-周期序列和奇數(shù)k≥3，得到了其k錯線性復(fù)雜度期望的上界和下界.而其k錯線性復(fù)雜度期望的精確值仍是有待研究的問題.

[1]RUEPPEL R A.Analysis and design of stream ciphers[M].Berlin:Springer-Verlag,1986:51-52.

[2]GAMES R A,CHAN A H.A fast algorithm for determining the linear complexity of a pseudorandom sequence with period 2n[J].IEEE Trans Inform Theory,1983,IT-29(1):144-146.

[3]STAMP M,.MATIN C F.An algorithm for the k-error linear complexity of binary sequences of period 2n[J].IEEE Trans Inform Theory,1993,39(4):1398-1401.

[4]KURSOSAWA K,Sato F,SAKATA T,et al.A relationship between linear complexity and k-error linear complexity[J].IEEE Trans Inform Theory,2000,46(2):694-698.

[5]MEIDL W,NIEDERREITER H.Counting functions and expected values for the k-error linear complexity[J].Finite Fields Appl,2002,8:142-154.

[6]MEIDL W,NIEDERREITER H.Linear complexity k-error linear complexity,and the discrete fourier transform[J].J.Complexity,2002,18:87-103.

[7]MEIDL W,NIEDERREITER H.On the expected value of the linear complexity and the k-error linear complexity of periodic sequences[J].IEEE Trans Inform Theory,2002,48(11):2817-2825.

[8]MEIDL W.On the stability of 2n-periodic binary sequences[J].IEEE Trans Inform Theory,2005,51(3):1151-1155.

THE BOUNDS OF EXPECTED VALUE OF k-ERROR LINEAR COMPLEXITY OF 2n-PERIODIC SEQUENCES

TANG Miao
（School of Science,Anhui Agricultural University,Hefei Anhui 230036）

For the 2n-periodic binary sequences with maximal linear complexity,the k-error linear complexity lie in some ranges，k≥3and k is an odd number，by research the number of sequences of each range，the upper and lower bounds of expected value of the k-error linear complexity of the specific periodic sequences are given.

linear complexity;k-error linear complexity;periodic sequences;bound

O236.2 < class="emphasis_bold">文獻(xiàn)標(biāo)識符：

符：A

1672－2868（2011）03－0001－04

2011-2-20

安徽農(nóng)業(yè)大學(xué)校青年科學(xué)基金資助項目（項目編號：2009zr29）

唐 淼(1981－)，男，安徽合肥人。安徽農(nóng)業(yè)大學(xué)講師，研究方向：編碼與密碼

責(zé)任編輯：陳 侃