第三章 周期单序列及其对偶序列的线性复杂度
本章介绍了周期单序列线性复杂度基础知识，利用F2上二元周期序列及其对偶序列的极小多项式，生成函数和线性复杂度之间关系的已有结论，在Fp（p为素数）上提出p元周期序列的对偶序列的基础上，讨论了p元周期序列及其对偶序列的极小多项式之间的关系，并计算出p元周期序列及其对偶序列的线性复杂度之间的关系。
3.1 周期单序列线性复杂度基础知识
周期序列的线性复杂度是度量流密码强度的一个重要指标,序列,S??(s,,?,的线性复杂度定义为生成它的最小线性反馈移位寄存器的长度)0,s1?Ns?1记为: LC(S?)。从线性复杂度的定义可知，如果一个序列的线性复杂度为L，则只
需知道该序列的任意2L个连续元素，即可通过解线性方程组或借助B?M算法[25，28]找到该序列所满足的齐次线性递归关系式，进而可确定整个序列。这说明密钥流序列的齐次线性复杂度必须足够大，才能保证流密码系统的安全性。因而线性复杂度是度量密钥流序列的密码强度的一个重要指标，但是线性复杂度高的序列未必是“好”的密钥流序列。
例如: SN?1111?10，LC(SN)?N?1但是只要把序列中的一个字节“0”改为“1”,则序列的线性复杂度就降为1。设fs(x)是生成SN的极小多项式,则
LC(SN)?N?deg(gcd(SN(x),1?xN))?? [29]
。由此可见讨论序列的极小多项式有十分重要
的意义。由于序列S?的对偶序列S是一类特殊的序列,且与S?有着密切的关系,则研究S的极小多项式有一定的应用价值。文[30]讨论了F2上的序列S?与其对偶序列
??本节将在此基础上讨论F上序列S与其对S的生成函数及极小多项式之间的关系。
偶序列S的生成函数及极小多项式之间的关系，并且计算出Fp上序列S与其对偶序列S之间的线性复杂度的关系。
设SN表示有限域Fp上有限序列(S0,S1,?,SN?1)，S?表示Fp上无限序列
，使SN（或S?）(S0,S1,?,SN?1,?)，设有整数L和Fp上一组数c1,c2,?,cL（p是素数）
满足：Sj?c1Sj?1?c2Sj?2???cLSj?L?0,j?L (1),则称SN（或S?）是一个L阶齐次线性递归序列，L是SN（或S?）所满足的齐次线性递归关系的最小阶数，称为SN（或
S?）的线性复杂度，记为：LC(SN)（或LC(S?)）。
??p?对于序列S?和SN,它们的生成函数定义为:
S(x)?S0?S1(x)?????SNx??????Sixi和SN(x)?S0?S1x?????SN?1xN?1。
Ni?0?如果S?是周期为
S(x)?S(x)(1?x?xNN2NN
的序列, SN是它的第一个周期,则
SN(x)??)?,则: S(x)可以表示成:
1?xN8
rs(x)SN(x)/gcd(SN(x),1?xN) S(x)?。 ?(1?xN)/gcd(SN(x),1?xN)fs(x)这里
fs(x?)?x(N1s)Nx/?gxcrsNdx(?sx(N),s1xNN然?x),。显
rs(x)fsx/是既约的, deg(rs(x))＜deg(fs(x)),fs(x)为S?的极小多项式, deg(fs(x))=LC(S?)为S?的线性复杂度
[31]
。
3.2 二元周期单序列及其对偶序列线性复杂度
引理3.2.1[29] 设S?是满足Sj?c1Sj?1?c2Sj?2?????cLSj?L?0, j?L的L阶 二元递归序列（或称伪随机序列），则生成函数S(x)可表示为s(x)?g(x)/f(x),其中f(x)?c0?c1x???cLx 为S的一个生成函数，且：g(x)??(?sj?ici)xj。
L?L?1j?0ji?0反之，若g(x)为F2上的一个次数deg(g(x))?l的多项式，且
)g(x)/的f幂x级数是一个满足f(x)?c0?c1x???cLxL，则s(x?Sj?c1Sj?1?c2Sj?2?????cLSj?L?0, j?L递归关系的齐次线性递归序列的生成函
数。
关于生成多项式与极小多项式有引理3.2.2：
引理3.2.2[29]设S?是周期为N的序列，则其生成函数可表示为:
rs(x)SN(x)/gcd(SN(x),1?xN)?NN?1S，其中，且的S(x)??s(x)?s?sx?????sx01N?1NNN(1?x)/gcd(S(x),1?x)fs(x)极小生成多项式为 fs(x)?(1?xN)/gcd(sN(x),1?xN)。
结合引理3.2.1和引理3.2 .2可知，周期序列的生成函数的既约有理表达式唯一，且既约有理形的分母一定是其极小多项式。
设 F2上二元序列S??(S0,S1,?,SN?1,?)，下面以S表示S?按位取反所得的
?)，这里Si?1?Si,i?0,1,2序列S?(S0,S1,S2,?，对于S?与S的生成多项式与
???极小多项式有下列定理：
定理3.2.1
[30]
设F2上周期序列S生成函数S(x)??Sixi ?rs(x)/fs(x)，其
??i?0中gcd(rs(x),fs(x))?1且fs(x)是S的极小多项式，记fs(x)??cjxj(c，0?cm?1) j?0?m以l记x?1为fs(x)根的次数(l?0)，即fs(x)?(1?x)lf(1x)，其中f1(1)?0，则对S?的按位取反所得的序列S的生成函数：
? 9
?(1?x)rs(x)?fs(x),?f(x)(1?x)s?(1?x)rs(x)?fs(x)?(rs(x)?f1(x))/(1?x)S(x)???,fs(x)(1?x)f1(x)??rs(x)?f1(x),?fs(x)??(1?x)fs(x),?f1(x),S?的极小多项式为: fs(x)???fs(x),?l?0l?1
l?2l?0l?1 l?2l?0l?1 l?2
?L(s)?1,?推论3.2.1[30]在上述记号下:L(s)??L(s)?1,?LC(s),?定理3.2.2 [30]F2[x]中的n次不可约多项式fs(x)生成的n阶伪随机序列
S?的对偶序列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。
?定理3.2.3[30]F2[x]中的n次本原多项式fs(x)生成的n阶m序列S?的对偶 序列S的极小多项式为(1?x)fs(x)，且线性复杂度为n+1。
以上讨论了F2上关于周期序列S?与其对偶序列S的生成函数，极小多项式及线性复杂度之间的关系的已有结论。下面将讨论Fp上周期序列S?与其对偶序列S的生成函数及极小多项式之间的关系，并且计算出Fp上周期序列S?与其对偶序列S之间的线性复杂度的关系。
3.3 P元周期单序列及其对偶序列线性复杂度
定义3.3.1 设S?是满足式(1)的p元序列，则f(x)?c0?c1x?????cLxL 为S?的一个特征多项式或生成多项式，其中c0?0,ci?Fp,i?1,2,???L，并且其中
????cL?0。S?的生成多项式中次数最小的多项式称为S?S?的极小多项式，并记为fs(x)。S所对应的生成为S(x)??Sixi。
??i?0定义3.3.2 设Fp上p元序列S??(S0,S1,S2,?)，称S?(S0,S1,S2,?)为
S?的对偶序列，其中Si?(p?1)?Si,i?0,1,2,?。
?引理3.3.1[29]设S?是周期为N的序列，则其生成函数可表示为：
10
NNNNNN??s(x)??sixi??s(x)/gcd(s(x),1?x)/1?x/gcd(s(x),1?x)?????
i?0?其中sN(x)?s0?s1x?????sN?1xN?1，且S?的极小多项式为:
fs(x)?(1?xN)/gcd(SN(x),1?xN)。
周期序列的生成函数的既约有理表达式唯一，且既约有理形的分母一定是其极小多项式。
对于Fp上的序列S?与S的生成函数与极小多项式有：
定理3.3.1 设Fp上周期序列S?的极小多项式为fs(x)?(1?x)tg(x)，
i?0其中t为非负整数g(1)。S的生成函数S(x)??S?ix???s其r()x/sf(,x)中
i?0S?的对偶序列S的生成函数： gcdrs(x(f)s,x(?)，则)??(p?1)g(x)?rs(x)(1?x)?(1?x)g(x)?(p?1)fs(x)?rs(x)(1?x)?(p?1)(1?x)g(x)?rs(x)(1?x)??S(x)?2(1?x)g(x)(1?x)fs(x)??(p?1)(1?x)tg(x)?rs(x)(1?x)?(1?x)t?1g(x)?,t?0,t?1 ,t?2?(1?x)fS(x)?1??fS(x)?的极小多项式为: SfS(x)??1?x?fS(x)???fS(x)???ii,t?0
,g(1)?rS(1)?pt?1,g(1)?rS(1)?pt?1,?iit?2?isN(x)证明 S(x)??six??(p?1?si)x??(p?1)x??six?(p?1)?x? N1?xi?0i?0i?0i?0i?0而?xi?1?x?x2???i?0?1，则 1?xS(x)?(p?1)r(x)(p?1)fs(x)?rs(x)(1?x)1 ?s?1?xfs(x)(1?x)fs(x)??(p?1)fs?x??rs(x)(1?x)??/gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)??
?(1?x)fs(x)?/gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?
由引理3.3.1知S的极小多项式fs(x)为:
?fs(x)?(1?x)fs(x)/gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?
11
接下来只需证明
?1?(1?x)2?gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)????1?x??1?x(1) 当t?0时,fs(x)?g(x)
,t?0,g(1)?rs(1)?pt?1
,g(1)?rs(1)?pt?1,t?2gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?
gcd?(p?1)g(x)?rs(x)(1?x),(1?x)g(x)?
?gcd?(1?x),(p?1)g(x)?rs(x)(1?x)??gcd?g(x),(p?1)g(x)?rs(x)(1?x)? ?gcd?(1?x),(p?1)g(x)??gcd?g(x),rs(x)(1?x)? =1
则fs(x)?(1?x)fs(x)
t(2)当t?1时，fs(x)?(1?x)g(x),g1()?0，
gcd?(p?1)fs(x)?rs(x)(1?x),(1?x)fs(x)?
tt?1?gcd?(p?1)(1?x)g(x)?r(x)(1?x),(1?x)g(x)?s?? t?1t?(1?x)gcd??(p?1)(1?x)g(x)?rs(x),(1?x)g(x)??
tt?1t?1?(1?x)gcd??(1?x),(p?1)(1?x)g(x)?rs(x)???gcd??g(x),(p?1)(1?x)g(x)?rs(x)?? i 当t=1时
tt?1 gcd?(1?x),(p?1)(1?x)gx(?)rsx(?)??
1?x), ?gcd??p?1?g(x)?sr(x??(?)
?gcd?(1?x),g(x)?rs(x)?
① 当g(1)?rs(1)?p时：
gcd?(1?x),g(x)?rs(x)??1?x
t?1gcd??g(x),(p?1)(1?x)g(x)?rs(x)??
?gcd?g(x),(p?1)g(x)?rs(x)??1
tt?1t?1gcd?(1?x),(p?1)(1?x)g(x)?r(x)?gcdg(x),(p?1)(1?x)g(x)?rs(x)???s????
?1?x
fs(x)?(1?x)fs(x)/(1?x)2?② 当g(1)?rs(1)?p时：
1fS(x) 1?xgcd?(1?x),g(x)?rs(x)??1
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) ⅱ 当t?2时：
12