tt?1t?1gcd??(1?x),(p?1)(1?x)g(x)?rs(x)???gcd??g(x),(p?1)(1?x)g(x)?rs(x)???1
fs(x)?fs(x)
证毕.
推论3.3.1：在上述记号下
?LC(S)?1?LC(S)?1? LC(S)???LC(S)??LC(S),t?0,g(1)?rs1()?pt?1
,g(1)?rs(1)?pt?1,t?2
证明 由定理3.3.1直接可以证出。定理3.3.2 Fp?x?中的n次不可约多项式
?fs(x)生成的n阶伪随机序列S?的对偶序列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。
证明 因为fs(x)在域FP上不可约，则 gcd((1?x),fs(x))?1,即t=0,由定理3.3 .1得：fs?(1?x)fs(x),则由推论3.3.1得证。
定理3.3.3 Fp?x?中的n次本原多项式fs(x)生成的n阶m序列S?的对偶序?
列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。
证明 Fp?x?中的n次本原多项式fs(x)为不可约多项式，则由定理3.3.2直接可以得证。
13
第四章 2n?周期二元序列的4-错线性复杂度
本章介绍了周期单序列k-错线性复杂度的基础知识，利用F2上线性复杂度为2n?1的2n?周期二元序列的2-错（或3-错）线性复杂度的已有结论，进一步讨论了线性复杂度为2n?1的2n?周期二元序列的4-错（或5-错）线性复杂度的，并计算出相应的期望值。
4.1 周期单序列k-错线性复杂度基础知识
周期序列的线性复杂度和k-错线性复杂度是度量流密码强度的两个重要指标,序列S??(s0,s1,?,sN?1,?)的线性复杂度定义为生成它的最小线性反馈移位寄存器的长度,记为: LC(s?)。从线性复杂度的定义可知，如果一个序列的线性复杂度为L，则只需知道该序列的任意2L个连续元素，即可通过解线性方程组或借助B?M算法找到该序列所满足的齐次线性递归关系式，进而可确定整个序列。这说明密钥流序列的齐次线性复杂度必须足够大，才能保证流密码系统的安全性。因而线性复杂度是度量密钥流序列的密码强度的一个重要指标，但是线性复杂度高的序列未必是安全的密钥流序列。例如: SN?1111?10,LC(SN)?N?1,但是只要把序列中的一个字节“0”改为“1”,则序列的线性复杂度就降为1，即这个序列的稳定性较差。上世纪80年代末，丁存生和肖国镇等提出了重量复杂度，球体复杂度，函数稳定性等一系列密码稳定性的重要指标，进一步推进了序列的安全性研究。后来Stamp和Martin提出了类似球体复杂度的线性复杂度稳定性指标，即k-错线性复杂度。
设S??(s0,s1,?,sN?1,?)是N?周期序列，k是非负整数，定义N?周期序列S?的
???k?错线性复杂度LCN,K(S?)?minLC(S?T)，其中，T?(t0,t1,?,t,)，N?1??WN(T)?K[8]
显然K=0时，k-错线性复杂度就是序列的线性复杂度。WN(T?)是序列T?的汉明重量。
在文献[12]中，Kurosawa等给出2n?周期二元序列S的K-错线性复杂度严格小于线性复杂度LC(S)的最小值为：Kmin?2WH(2n?LC(S))其中WH(b)指整数b在二进制表示下的
nK?2n?汉明重量。在2002年，W. Meidl给出更低的界：EK?2?2?log2(???)，其中EKt?0?t?表示2n?周期二元序列的k?错线性复杂度的期望值[26]。在文献[32]中进一步指出了EK的范围：
?2n?n?1?2t?tK?2t?EK?2?3?2n?????2?? ?j2j?0??t?2j?0?j?2n?1?1K?2n?1n?1?2t?tK?2t?nEK?2?3?????2?? ??2n2t?22j?0?j?j?0?j?n1K当K?0时，Rueppel给出线性复杂度为L的2n?周期二元序列的具体个数
14
N(L):N(0)=1, N(L)?2L?1(1?L?2n)，且E0?2n?1?2[25]
?2n。当K?1Wilfried。,2时，
Meidl给出线性复杂度为2n的2n?周期二元序列的k?错线性复杂度的期望值[32]：
E1?2?3?2n?2n(2?1)??2?2?r。当K?2,3时，在文献[33]中讨论了线性复杂度为
nr?2n?1r2n?1的2n?周期二元序列相关结论令
Lr,c?2?2N2(0)?22n?2nr?1?c，(2?r?n?1,1?c?2?2)n?2n?2nr，
n?1N2(Lr,c)?22rn?2r?1?2r?c?1，
，并计算出：E2LC(S)?2n?1?2?7?2??2?2?2r?1。
r?3本节将在此基础上进一步讨论k?4,5时的相关结果。
设SN表示有限域F2上有限序列(S0,S1,?,SN?1)，S?表示F2上无限序列
(S0,S1,?,SN?1,?)，设有整数L和F2上一组数c1,c2,?cL，使SN（或S?）满足：
Sj?c1Sj?1?c2Sj?2???cLSj?L?0,j?L ,则称SN（或S?）是一个L阶齐次线性递归序列，L是SN（或S?）所满足的齐次线性递归关系的最小阶数，称为SN（或S?）的线性复杂度记为：LC(SN)（或LC(S?)）。对于序列S?和SN,它们的生成函数定义为:
?S(x)?S0?S1x???SNx????Sixi 和 SN(x)?S0?S1x???SN?1xN?1。
Ni?0若S?是周期为N的序列, SN是它的第一个周期,则
S(x)?S(x)(1?x?xNN2NSN(x)??)?,故S(x)可以表示成:
1?xNN(?1xrS(x)SN(x)gcd(SN(x),1?xN)这里fS(x)S(x)???(1?xN)gcd(SN(x),1?xN)fS(x)rS(x))?rS(x)?SN(x)gcd(SN(x),1?xN)，显然deg()NgScdx(?N，(x),1)是deg(fSx(r)),x(Sf)x(既)约的, SfS(x)为S?的极小多项式,LC(S?)?deg(fS(x))?N?deg(gcd(SN(x),1?xN))为S?的线性复杂度[34]。对于一个2n?周期二元序列S，它的线性复杂度LC(S)可以由Chan-Games算法确定。Chan-Games算法在文献[8]中总结出计算2n?周期二元序列的k?错线性
[5]
复杂度的方法，其中K是定值，且对于所有K都适合。本文主要利用Chan-Games算法展开讨论。
下面简要介绍一下Chan-Games算法：
令S(n)?(S0,S1,?,S2n?1)是S?的第一个周期序列，则LC(S(n))?LC(S?)，把S(n)分成左右两半部分，分别记为：
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)))，并记S(n?1)?L(S(n)；
15
（2） 若L(S(n))?R(S(n))，则LC(S?)?2n?1?LC(S(n?1))，其中
显然S(n?1)是长为2n?1的序列，其中各元素的加法运算在F2S(n?1)?L(S(n))?R(S(n))。中进行。
当n?1时，Chan-Games算法定义了从F2n到F2n?1上的映射?n：
2
2?n((S0,S1,?,S2?1))?(S0?S2,S1?S2?1,?,S2由映射?n的定义可以得到以下性质：
nn?1n?1n?1?1?S2n?1)
P
1
：W(?n(S(n)))?W(S(n))；
：W(?n(S(n)))?W(S(n))(mod2)，其中n?2；
nPP
2?1(n)(n)(n)2?(S)?{v?F|?(v)?S}S：的原象有个元素。 2n?1n?1n?1232n4.2 线性复杂度为2n?1的2?周期二元序列的2-错（或3-错）线性复杂度
引理4.2.1[35] 令S是周期N?2n的二元序列，则LC(S)?2n，当且仅当W(S)是奇数。
引理
4.2.2[35]令S(n)?(S0,S1,?,S2n?1)是周期N?2n的二元序列，
[35]
LC(S(n))?2n?2，当且仅当S0?S2???S2n?2?S1?S3???S2n?1?0。
引理4.2.3
n在F2上不存在两个2?周期二元序列a?(a0,a1,?,a2n?1)?和
b?(b0,b1,?,b2n?1)?有相同的线性复杂度C(1?C?2n?2)，且满足au?bu，av?bv，
ai?bi(u?v,0?i?2n?1,i?u,v)，其中u?v(mod2)。
n定理4.2.1[35] 设S是线性复杂度为2n?1的2?周期二元序列,记
LC4(S)?Lr,c,对于所有形如: Lr,c?2n?2r?1?c，(2?r?n?1,1?c?2r?2)的整数 有:N2(Lr,c)?22n?2r?1?2r?c?1且N2(0)?22n?2 .如果L?0,且不是Lr,c的形式,则不存在
n线性复杂度为LC(S)?2n?1,且LC4(S)?L的2?周期二元序列S。
n定理4.2.2 [35]线性复杂度为2n?1(n?3)的2?周期二元序列的2?错线性
复杂度的期望值为：
E2LC(S)?2n?1?2?7?2n?2n?2n??2?2?2r?1
r?3n?1r
n4.3 线性复杂度为2n?1的2?周期二元序列的4-错（或5-错）线性复杂度
引理4.3.1 令S是周期N?2n的二元序列，则LC(S)?2n，当且仅当W(S)是奇数。
证明 由LC(S)?deg(fS(x))?N?deg(gcd(SN(x),1?xN))得：
16
LC(S)?2n?gcd(x2?1,SN(x))?1?gcd(SN(x),1?xN))?1?SN(1)?1?W(S)是奇数。
引理
4.3.2[35]令S(n)?(S0,S1,?,S2n?1)是周期N?2n的二元序列，
nLC(S(n))?2n?2，当且仅当S0?S2???S2n?2?S1?S3???S2n?1?0。
n引理4.3.3[35]在F2上不存在两个2?周期二元序列a?(a0,a1,?,a2n?1)和
b?(b0,b1,?,b2n?1)有相同的线性复杂度C(1?C?2n?2)，且满足au?bu，av?bv，am?bm，an?bn和ai?bi(u?v?m?n,0?i?2n?1,i?u,v,m,n)，其中：u,v,m和n中有三个奇偶性相同,有一个奇偶性不同。
证明 令: a(n)(x)和b(n)(x)分别是序列a和b的生成函数，由
LC(S)?deg(fS(x))?N?deg(gcd(SN(x),1?xN))，且a与b有相同的线性复杂度C
nn得： a(n)(x)?a0?a1x???a2n?1x2?1?(1?x)2?ca?(x)
b(n)(x)?b0?b1x???b2n?1x2nn?1?(1?x)2n?cb?(x)
?x)?1其中：(a?(x),1，(b?(x),1?x)?1，由au?bu，av?bv，am?bm，an?bn得：
b(n)(x)?a(n)(x)?xu?xv?xm?xn?(1?x)2?ca?(x)?xv(1?xu?v)?xn(1?xm?n)， u,v,m和
n中有三个奇偶性相同,有一个奇偶性不同。不妨设:
u?v(mod2),m?n?v(mod2).u?v是奇数，且1?xnu?v?(1?x)?xj，则：1?x能被
j?0u?v?11?xu?v整除。但是((1故((1?x)2,b(n)(x))?1.由1?c?2n?2得：?x2),?1xu?v?).1n22?2n?c?2?1，则：(1?x)2?c能被b(n)(x)整除.这与((1?x),b(n)(x))?矛盾1.故原
命题得证。
n本部分主要讨论线性复杂度为2n?1的2?周期二元序列.由
Kmin?2WH(2n?LC(S))可知LC（S）减小，当且仅当K≥2.当K=2，3时，文献[35]已
经讨论.本文将进一步讨论K=4，5时的情况.由引理4.3.1知，W(S)为偶数.如果S中每个周期中改变五个字节，W(S)变为奇数，则LC(S)?2n。由此可见，
n对于线性复杂度为2n?1的2?周期二元序列，LC4(S)?LC5(S)。下面只需讨论
LC4(S)即可。
n定理4.3.1 设S是线性复杂度为2n?1的2?周期二元序列,记
r?2)的整数 LC4(S)?Lr,c ,对于所有形如: Lr,c?2n?2r?1?c(2?r?n?1,1?c?2nr?112n?2r?1?2r?c?1r?1?2?2r?c?1r?12(2?1)(2?2)?2有：N4(Lr,c)??2 31且N4(0)??(24n?4?22n?1)?23n?3?22n?2 。如果L≠0,且不是Lr,c的形式,则不存在
3n线性复杂度为LC(S)?2n?1,且LC4(S)?L的2?周期二元序列S。
证明 令S(n)?(S0,S1,?,S2n?1)是s的第一个周期序列，且LC(S)?2n?1。 由 Chan-Games算法知: L(S(t))?R(S(t)),LC(S(1))?1。其中
17