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

唐淼

（安徽農業大學理學院，安徽 合肥 230036）

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

唐淼

（安徽農業大學理學院，安徽 合肥 230036）

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

線性復雜度；k錯線性復雜度；周期序列；界

1 引言

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

2 預備知識

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

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

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

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

1） LC（S）=2n當且僅當W（s（n））為奇數；

2） LCk（S）=LCk+1（S），k 為奇數；

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

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

在文獻[2]中，Games和Chan給出了能夠快速計算2n-周期序列S的線性復雜度的算法，下面簡單的描述 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）））∞）.

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

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

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

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

3 錯線性復雜度期望的界

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

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

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

4 結束語

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

[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">文獻標識符：

符：A

1672－2868（2011）03－0001－04

2011-2-20

安徽農業大學校青年科學基金資助項目（項目編號：2009zr29）

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

責任編輯：陳 侃