二元周期序列的5错线性复杂度

周建钦，王传银

(杭州电子科技大学通信工程学院，浙江杭州310018)

0 引言

线性复杂度是衡量密钥流序列随机性的一个重要指标，但高线性复杂度并不能保证序列是安全的。如果改变序列的一个周期段中一个或几个元素，其线性复杂度发生很大的变化，则该序列仍然是密码学意义上的弱序列。为了解决这个问题，文献1引入了线性复杂度稳定性度量指标:k-错线性复杂度。文献2给出了2n-周期二元序列s的k-错线性复杂度严格小于线性复杂度L(s)的最小值:kmin=2WH(2n-L(s))，其中WH(b)表示整数b在二进制表示下的Hamming重量。文献3给出了线性复杂度为L的2n-周期二元序列的具体个数。文献4给出了当k=1，2时，线性复杂度为2n的2n周期二元序列的k-错线性复杂度分布情况。文献5给出了2n周期二元序列的3错线性复杂度分布的完整计数公式。本文通过将5错线性复杂度的计算转化为求Hamming重量最小的错误序列，讨论了线性复杂度为2n，周期为2n二元序列的5错线性复杂度分布情况，给出了5错线性复杂度为2n-3，2n-3+1和2n-3+2n-4的二元序列计数公式。

1 线性复杂度为2n二元序列的5错线性复杂度

定义1 设s(n)={s0，s1，s2，…，s2n-1}是二元序列s的第一周期，n≥1，根据Games-Chan算法，定义映射φn从到

引理1 定义1的映射φn满足下面的性质［4］:

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

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

引理 2 设 N(L)表示周期为 2n，线性复杂度为 L的二元序列个数［3］，则 N(L)

引理3 设s(n)，t(n)是2个不同的二元序列但线性复杂度均为c，1≤c〈2n-3，n〉3，u(n)，v(n)是2个不同的二元序列但线性复杂度均为2n，且u(n)，v(n)的非零元素个数分别为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)不同。

因为s(n)，t(n)是2个不同的二元序列但线性复杂度均为c，1≤c〈2n-3，n〉3，所以s(n)+t(n)的线性复杂度小于2n-3，且s(n)+t(n)的2n个元素可以分成8个相同的部分。

假设u(n)+v(n)和s(n)+t(n)相同，则u(n)+v(n)的2n个元素可以分成8个相同的部分，故u(n)+v(n)的非零元素个数只能为8，u(n)+v(n)的线性复杂度为2n-3，与s(n)+t(n)的线性复杂度小于2n-3矛盾。

给出具有给定5错线性复杂度的2n周期二元序列个数的具体表达式:

定理1 设N5(2n-3)表示周期为2n，线性复杂度为L(s)=2n，5错线性复杂度为2n-3的二元序列s的个数，n〉3，则 N5(2n-3

证明 设序列s(n)是线性复杂度为2n-3的二元序列，则由引理2知s(n)的个数为n=5。

设二元序列u(n)的线性复杂度为2n且W(u(n))=1，可知u(n)+v(n)的5错线性复杂度为2n-3。

设序列u(n)的线性复杂度为2n且W(u(n))=3，且u(n)中任意两个非零元素距离为2n-3的倍数，易知恰好存在一个序列v(n)且W(v(n))=5，使得u(n)+v(n)的线性复杂度为2n-3，即u(n)+s(n)的5错线性复杂度小于2n-3。

设序列u(n)的线性复杂度为2n且W(u(n))=5，且u(n)中至少4个非零元素距离为2n-3的倍数，易知恰好存在一个序列 v(n)，使得 u(n)+v(n)的线性复杂度为2n-3，即u(n)+s(n)的5错线性复杂度小于2n-3。

设序列u(n)的线性复杂度为2n且W(u(n))=3，则u(n)的个数为

设序列u(n)的线性复杂度为2n，W(u(n))=3，且u(n)中任意两个非零元素距离为2n-3的倍数，则u(n)的个数为

设序列u(n)的线性复杂度为2n且W(u(n))=5，则u(n)的个数为

设序列u(n)的线性复杂度为2n，W(u(n))=5，且u(n)中恰好4个非零元素距离为2n-3的倍数，则u(n)的个数为

设序列u(n)的线性复杂度为2n，W(u(n))=5，且u(n)中任意5个非零元素距离为2n-3的倍数，则u(n)的个数为

故5错线性复杂度为2n-3的二元序列s的个数为

例如，当n=4时，N5(24-3)=7 200，即线性复杂度L(s)=24，5错线性复杂度为2的二元序列s的个数为7 200，通过计算机验证可得同样的结果。

定理2 设N5(2 +1)表示周期为2，线性复杂度为L(s)=2，5错线性复杂度为2 +1的二元序列s的个数，n〉4，则

与定理1证明方法类似，只需考虑更复杂的重复情况即可。

定理3 设N5(2n-2-2n-4)表示周期为2n，线性复杂度为L(s)=2n，5错线性复杂度为2n-2-2n-4的二元序列s的个数，n〉3，则

与定理1、2证明方法类似，只需考虑更复杂的重复情况即可。

2 结束语

通过研究周期为2n的二元序列线性复杂度，将具体5错线性复杂度值所对应的原序列的计数转化为求Hamming重量最小的错误序列的个数。基于Games-Chan算法，本文讨论了线性复杂度为2n的2n周期二元序列的5错线性复杂度分布情况，给出了若干具体5错线性复杂度对应原序列个数的计算公式。基于上面的讨论，对随机周期序列的线性复杂度和k错线性复杂度的统计性质［6］，也可研究线性复杂度为2n的2n周期二元序列的5错线性复杂度对应原序列个数的期望值。

［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］ 苏明.周期序列复杂度的分布［D］.天津:南开大学，2004.