S(t)??t?1????n(S(n))?(S0(t),S1(t),???,S2t?1(t)),
S(t)i?2n?t?j?0?1Sj2t?i(2?t?n,0?i?2t?1)显然S(1)?(1,1),
则: S0?S2???S2n?2?1 (1)
S1?S3???S2n?1?1 (2)
令:a是s改变4个字节后得到的新的序列, a(t)的获得与S(t)一样(2?t?n). 由引理4.3.1知，W(S)是偶数，则a(t)与S(t)最多有4个字节不同. 接下来分三种情况讨论：
(ⅰ)当W(S)?W(s)?2时，显然：LC4(0)?LC2(0)是最小的。
由等式（1），（2）可知：1??S0,S2,???,S2n?2?，且集合?S0,S2,???,S2n?2?中只有一个“1”，同样，集合?S1,S3,???,S2n?1?中也只有一个“1”。故满足以上条件的序列S总共有：2n?1?2n?1?22n?2个，即：N4(0)?N2(0)?22n?2。 (ⅱ)当W(S)?W(S(n))?4时，显然：LC4(0)是最小的。 以下分两种情况讨论：
①1?{s0,s2,...,s2n?2}，且集合{s0,s2,...,s2n?2}中只有一个“1”， 1,1,1?{s1,s3,...,s2n?1}，
2且集合{s1,s3,...,s2n?1}只有3个“1”。则：满足以上条件的序列S总共有： 2n?1(3)n?1(n)个。
②1?{s1,s3,...,s2n?1}，且集合{s1,s3,...,s2n?1}中只有一个“1”， 1,1,1?{s0,s2,...,s2n?2}，且集合{s0,s2,...,s2n?2}中只有三个“1”， 则：满足以上条件的序列S总共有：
22n?1(3)个。
n?1综合①，②得：N4(0)?2(n?12n?13)?2(n?12n?131)?(24n?4?22n?1)?23n?3 31由(ⅰ)，(ⅱ)可知：N4(0)?(24n?4?22n?1)?23n?3?22n?2
3(ⅲ)当W(S)?W(S(n))?4时：
由?n的性质P2知W(S(t))(2?t?n)是偶数。令r是使得W(S(r))?4的最大整数，其中1?r?n?1，则对于所有r?j?n，W(L(S(j?1))?R(S(j?1)))?W(S(j))?4，即： 且S改变四个字节对应S(j)改变四个字L(S(j?1))和R(S(j?1))至少有四个字节不同，
节。 a(j?1)是S(j?1)最多改变四个字节所得到的序列。由L(a(j?1))?R(a(j?1))得
LC4(S)?2n?1?2n?2???2r?1。 接下来分两种情况讨论：
① 若S(n)中改变四个字节，恰好对应S(r?1)有四个字节改变使得
18
L(a(r?1))?R(a(r?1))，则a的线性复杂度满足下列形式：
(r?1)))。否则,若 Lr,c?2n?1?2n?2???2r?1?c，1?c?2r，其中C?LC(L(aL(a(r?1))?R(a(r?1))，a(r)是非零向量，则：a的线性复杂度LC?满足：
LC??2n?1?2n?2???2r?1?2r?Lr,c由LC4(S)是S(n)中改变四个字节得到的最小线性复杂度知LC4(S)?Lr,c。下面令a的线性复杂度为最小值LC4(S)?Lr,c。
(r?1)其中：C?LC(L(a))，且L(a(r?1))?R(a(r?1))。
)接下来说明C?2r?2，令：S(r)?(S0(r),S1r(,...,S2rr(?1))，且W(S(r))?4。设：
S(r)?(0,?,0,1,0,?,0,1,0,?,0,1,0,?,0,1,0,?,0) (3)
????uvmn其中，0?u?v?m?n?2r?1。由S(r)??r?1(S(r?1))得：
(r?1)(r?1)S(r?1)?(S0,S1(r?1),...,S2)，且满足： r?1?1(r?1)(r?1)(r)(r?1)(r?1)(r)(r?1)(r?1)(r),,Su?Su?1S?S?1S?S?1， r?Sur?Svr?Smvm?2v?2m?2(r?1)(r?1)(r)Sn?Sn?1 (4) r?Sn?2rr?1)(r)，0?t?2?1,2t?u,v,m,n。 St(r?1)?St(??S?0rt2(r)(r)(r)由L(a(r?1))?R(a(r?1))，且S(r)应该变为a(r)?0得Su应该变为0。由等,Sv(r),Sm,Sn(r?1)(r?1)r?1)(r?1)(r?1)(r?1)(?1)式(4)知Su，Sv(r?1)?Sv(?，Sm，和Sn应该变为0。若?Su?Sm?Snr?2r2r?2r?2r(1)?(1)r?(1)r?a(r?1)?(a0r(?1),a1r?,...,a2ra,a,r01?1((r?1)1)r?(S是由改变四个字节得到的，则可,...,a2)r?1(r?1)(r?1r)(r?1)以适当选择位置Su使得下列等式成立： ,Sv(r?1),Sm,Sn(r?1)(r?1)(r?1)a0?a2?....?a2?0 (5) r?2(r?1)(r?1)(r?1)a1?a3?....?a2?0 (6) r?1r对于长为2r的序列L(a(r?1))，由引理2知：C?LC(L(a(r?1)))?2，则二元序列?2S的4?错线性复杂度LC4(S)是形如：
Lr,c?2n?2r?1?c(2?r?n?1,1?c?2r?2)的整数，其中r=1时，C没有意义。 接下来计算满足线性复杂度为2n?1，LC4(S)?Lr,c的2n?周期二元序列S的总数。
(r))由(1)，(2)和(3)知：S0 ?S2(r)?....?S2rr(?2?S0?S2?...?S2n?2?1(r)(r)S1(r)?S3?....?S2?S1?S3?...?S2n?1?1，这里，u,v,m和n的取值情况与r?1W(S(n))?4时相似。
由以上讨论结果可知：对于固定的S(r)和线性复杂度为C的L(a(r?1))，L(a(r?1)))是由L(S(r?1)通过适当改变Su(r?1),Sv(r?1),Sm(r?1)和Sn(r?1)而得，故由L(S(r?1))变为)共有16种情况。对于定值C，1?c?2r?2，由文献[40]知，L(a(r?1))共L(a(r?1)(r?1)有2c?1种选择，可使LC(L(a))?C。由引理4。3。3知，不存在两个2r?周期
序列仅仅只有四个字节不同，却有相同的线性复杂度C (1?c?2r?2)。R(S(r?1))完全由L(S(r?1))确定。所以对于固定的S(r)和C，S(r)的原象有16?2c?1?2c?3种选择使得S(r?1)改变后的序列线性复杂度为C。
19
r?12??(r)rS当W(S)?4时，与情况1类似。 的个数为2??，则利用?n的性质P3知，
3??2r?1??12n?12n?22rc?1r?共有2?2?2?2?2??条序列S满足：且LC4(S)?Lr,c，LC(S)?2n?1，??16?3?(r)其中1?c?2r?2。 故N4(Lr,c)?22n?1?22n?2?22r?1?2r?1??2?2????16
3??c?1r?11nr?1?22?2?2r?c?1(2r?1?1)(2r?1?2)(2?r?n?1,1?c?2r?1?2) 3② 若S(n)中改变四个字节，恰好对应S(r?1)有两个字节改变使得：
L(a(r?1))?R(a(r?1))
这种情况的讨论与情况①类似，可参见文献[44]得出：
N4(Lr,c)?22?22?22?22r?2?2c?1?4?22n?1n?2r?1n?2r?1?2r?c?1
nr?11nr?1综合①，②可知：N4(Lr,c)?22?2?2r?c?1(2r?1?1)(2r?1?2)?22?2?2r?c?1
3定理4.3.2 线性复杂度为2n?1（n≥3）的2n?周期二元序列的4?错线性复杂度的期望值为：
E4|LC?s??2n?1?22?2(T1?T2?T3?T4?T5?T6)
n其中: T1?22n?n?1n?1r?23n?22r?2(22?1?2)(2r?1?1)(2r?1?2)
r?1r22?2n?13r?2r?12r?1T2?(2?2)(2r?1?1)(2r?1?2) ?23r?222?1n?12r?2r?12r?r?12r2r?1T3?2(2?2?2?2)(2r?1?1)(2r?1?2) ?3r?2nT4?2T6?22n?n?1?2r?2n?12r?2r?1(2r2r?1?2)；T5?2?23r?2(22?1?2)
r?2rr2nn?1r?1r2n?1?22r?2(22?r?1?22?22?1?2)
r?2n?1r?1证明 22n?2E4|LC?s??2n?1???N4(Lr,c)Lr,c
r?2c?1n?12r?2n?12r?21nr?1nr?1???????22?2?2r?c?1(2r?1?1)(2r?1?2)?22?2?2r?c?1??(2n?2r?1?c)r?2c?1?3?n?12r?21nr?112n?n?2r?1?2r?c?1r?1r?1????2(2?1)(2?2)????22?2?3r?c?2(2r?1?1)(2r?1?2)r?2c?13r?2c?13n?12r?2
20
n?12r?2nr?112n?2r?1?2r?c?1r?1r?1????c?2(2?1)(2?2)???22?n?2?2r?c?1r?2c?13r?2c?1n?12r?2n?12r?22n?2r?1?3r?cn?12r?2n???2r?2c?1???c?22r?2c?1?2r?1?2r?c?1
?T1?T2?T3?T4?T5?T6
其中
2r?212n?n?2r?1?2r?c?1r?112n?n?1n?12r?2r?1r?1r?1r?1T1????2(2?1)(2?2)??2(2?1)(2?2)?2c?2r?2c?13r?2c?13n?12r?2
?22n?n?1n?1r?23n?12r?2?22r?2(22?1?2)(2r?1?1)(2r?1?2)
r?1r2r?212n?2r?1?3r?c?2r?112n?2n?13r?2r?1r?1r?1r?1T2????2(2?1)(2?2)??2?2(2?1)(2?2)?2cr?2c?13r?2c?1322?2n?13r?2r?12r?1?2(2?2)(2r?1?1)(2r?1?2) ?3r?2n?12r?212r?2nr?1r?11nn?1T3????c?22?2?2r?c?1(2r?1?1)(2r?1?2)??22?1.?22r?2(2r?1?1)(2r?1?2)??c?2c
r?2c?13r?2c?13mn由?j?2?(m?1)2jj?1nm?1?2,得?c?2c?(2r?3)?22c?12r?2r?1?2
22?1n?12r?2r?1?r2r?1?(2r?1?1)(2r?1?2) 故T3?.?2(2?3)?2?2??3r?2T4???22r?2c?1nn?12r?2n?n?2r?1r22?1n?12r?2r?12r?r?12r?2r?c?1?.?2(2?2?22?1?2)(2r?1?1)(2r?1?2)3r?2n
?22?n?1?2r?2n?12r?2r?12r?2c?1?2?2c2nn?1r?22n?n?1?22r?2(22?1?2)
r?2c2nn?1r?1rn?1r?1rT5???2r?2c?1n?12r?2n?12r?22n?2r?1?3r?c?2?2?23r?2r?12r?2c?1?2?2?23r?2(22r?22r?2c?1?1?2)r?1r
T6???c?2r?2c?12n?2r?1?2r?c?12n?1?2r?2n?12r?2r?1?c?2?2c2n?1r2?1(2?3)?2?2??22r?2??? r?2n?1?22n?1?2r?2n?12r?2r?1(2n2r?r?1?2?22r2r?1?2)
故 E4|LC?s??2n?1?22?2(T1?T2?T3?T4?T5?T6)
21
第五章 周期多序列及其广义对偶多序列的线性复杂度
本章介绍了周期多序列联合线性复杂度的基础知识，在此基础上分别提出了F2和Fp上周期多序列的广义对偶序列的定义，讨论了F2上二元周期多序列及其对偶序列的极小多项式之间关系，并计算出它们之间线性复杂度的关系；提出了F2上周期多序列的广义重量复杂度的定义, 在此基础上进一步讨论了周期多序列及其广义对偶多序列的广义重量复杂度之间的关系；接下来进一步讨论了Fp上p元周期多序列及其广义对偶序列的极小多项式之间的关系，并计算出它们之间线性复杂度的关系。
5.1 周期多序列联合线性复杂度基础知识
有限域上单序列的线性复杂度分析是流密码学密钥流序列的基本内容[6],很多学者研究了单序列线性复杂度以及序列的复杂度测量[36]。随着流密码学的发展,近年来以“字”或“向量”为单位的流密码渐渐引起重视,这些流密码学的理论要求研究多序列的联合线性复杂度。对于多序列的研究主要包括两个方面:一方面是多序列的分析,文献[37]中介绍了多序列的联合线性复杂度的综述;文献[18]研究了周期多序列的联合线性复杂度的期望值;文献[38]研究了一类特殊多序列的联合线性复杂度轮廓。文献[39,40]利用代数曲线构造了具有近乎优的联合线性复杂度轮廓性质的多序列。另一方面是对多序列的综合,即求多序列的极小多项式与联合线性复杂度。这是多序列中非常重要的问题。单序列的综合有B-M算法,连分式算法和欧几里德算法[6]等。文献[41,42]]中研究了多序列的综合及其在编码解码中的应用,Feng 等在文献[43,44]提出了广义欧几里德算法和迭代算法,后来许多学者也应用Gr?bner基理论来处理这个问题[45,46]。本文将在提出周期多序列的广义对偶多序列定义的基础上,讨论了二元周期多序列及其广义对偶多序列的极小多项式之间的关系,并且将进一步计算出它们之间的联合线性复杂度的关系。
设S是一个字长为t的以“字”为单位的序列,即S?(S0,S1,?),其中
Si?(a1i,a2i,?,ati),aji?F2,1?j?t,i?0,1,?,称S为F2上t-维多序列,当t?1时,即为通常所指的单序列。多序列S可以写成矩阵的形式:
a12???a21a22??,其中第i列为Si。
?????at1at2??用Aj?(aj0,aj1,aj2,?),j?1,2,?,t,那么S可以看成由t个“平行序列”构成的新?a10?aS?(S0,S1,?)??20????at0a11序列,并记: S?(A1,A2,?,At)。
在F2上t-维多序列S?(S0,S1,?),如果满足: Si?N?Si,i?0,则称正整数N是
22