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－)，男，安徽合肥人。安徽农业大学讲师，研究方向：编码与密码

责任编辑：陈 侃