现代密码学第6章 序列密码与移位寄存器

主要内容序列密码的基本原理移位寄存器与移位寄存器序列线性移位寄存器的表示线性移位寄存器序列的周期性线性移位寄存器的序列空间线性移位寄存器序列的极小多项式m序列的伪随机性B-M算法与序列的线性复杂度线性移位寄存器的非线性组合第6章序列密码与移位寄存器6.1序列密码的基本原理

由少量的随机密钥,通过移位寄存器以及非线性变换等多层编码环节，产生变化量大、复杂度高、随机性好的伪随机乱数，利用简单的密码法把它与明文数据串进行结合，从而实现对明文数据的加密。高杏欣:http:///link?url=cbStJk2vMO5eefDWdaHqG8TzROz9F60U18_vdlYX3iNcXlykWTDxZ8PRdFoy6ez-6YeTMVVG8FxUswEjajOlLK6.1序列密码的基本原理设明文、密钥、密文都是一个(0,1)序列，他们分别为则加密变换为解密变换为点击查看序列密码体制的模型6.2移位寄存器与移位寄存器序列一个q元域GF(q)上的n阶反馈移位寄存器由n个寄存器和一个反馈函数构成,如图所示.反馈移位寄存器的工作原理：

当一个时钟脉冲来临时,第i级寄存器的内容传送给第i-1级寄存器,i=2,3,·

·

·,n.第1级寄存器的内容为反馈移位寄存器的输出.反馈函数f的值传送给第n级寄存器.t≥0

时状态t+1

时状态反馈移位寄存器序列反馈移位寄存器的状态序列,点此查看定义6.1一、线性反馈移存器简介（一）基本概念

定义：反馈移存器的反馈逻辑电路可用一布尔函数来表示，若对应的布尔函数是线性函数，则称该反馈移存器为线性反馈移存器，否则称为非线性反馈移存器。P136定义6.11342123图1、线性反馈移位寄存器图2、非线性反馈移位寄存器图中存在与门器件，所以是非线性。（二）、工作原理假设在j时刻其内部状态为：在j+1时刻其内部状态变为：其中：此时的输出为j时刻的最高级：P135x3x1x2第7时刻001第0时刻001第1时刻100第2时刻110第3时刻111第4时刻011第5时刻101第6时刻010产生序列为：10011101……。a2a1

a0c1c2c3x1x2x3第0时刻100a0a1a2a3a4

a5a6=

0011101

第1时刻110第2时刻111第3时刻011第4时刻101第5时刻010第6时刻001第7时刻100第8时刻1106.3

线性移位寄存器的表示线性移位寄存器的一元多项式表示线性移位寄存器的矩阵表示点击各项查看详细的表示方法6.3

线性移位寄存器的表示0、线性递推式表示（补充内容）一个r级线性移存器的线性递推式表示为：an-1an-2an-3an-4ancr为1或者0的序列。6.3.1线性移位寄存器的一元多项式表示定义反馈函数：P1373.满足递推关系：2.定义输出序列：P1374.定义延迟算子D：P137最后一行……………5.定义：6.则：P138第二行公式:g(x)x4x3x2x1一个r级线性移存器的反馈多项式表示为：式子中1等于x06.3移位寄存器序列的表示(三种方法)：线性递推式（一元多项式）：

an+t=-c1at+n-1-c2at+n-2-…-cnat

联结多项式：

f(x)=1+c1x+c2x2+…+cnxn状态转移矩阵：满足：st+1=stTf

称st=(at,at+1,at+2,…,at+n-1)为n维状态实例（写出相应的线性递推式，画出移存器的逻辑框图）多项式

f(x)=1+c1x+c2x2+…+cnxn线性递推式：an=an-4+an-3+an-2当n=4时，则：a4=a0+a1+a2a3a2

a1

a0a3a2

a1

a0c1c2c3c4c1c2c3c4x1x2x3x4x4x3x2x1非退化的移位寄存器

若反馈函数形如：，其中，则称其为线性反馈寄存器；否则称其为非线性反馈移为寄存器。其中，若

我们说该寄存器是退化的，否则是非退化的。6.4线性移位寄存器序列的周期性定义6.2

设是GF(q)上的一个无穷序列,如果存在正整数p,使得对任意i≥0,都有则称为周期序列.满足该式的最小正整数称为该序列的周期,通常记为定理6.1

设是GF(q)上的一个无穷序列,p是一个正整数,如果对任意i≥0,都有成立则的周期一定整除p,即6.4线性移位寄存器序列的周期性定义6.3设

是一个GF(q)上的n阶线性移位寄存器序列.如果则称为GF(q)上的n阶m序列.定理6.2一个GF(q)上的n阶线性移位寄存器序列一定是周期序列,并且6.5线性移位寄存器的序列空间定理6.3

设f(x)

是GF(q)

上的一个常数项为1的一元n次多项式,则由f(x)所确定的线性移位寄存器的序列空间G(f)

是GF(q)

上的一个n

维线性空间.定理6.4

设f(x)和h(x)是GF(q)上的两个常数项为1的一元多项式.如果f(x)|h(x),即f(x)整除h(x),则由f(x)所确定的线性移位寄存器的序列空间G(f)是由h(x)所确定的线性移位寄存器的序列空间G(h)的子空间,即G(f)⊆G(h).定义：若存在f(x),g(x)，使得h(x)=f(x)g(x)，则称h(x)是可约多项式；否则，称其为不可约多项式。定理6.4：若f(x)|h(x)，则G(f)G(h).例1：联结多项式为

h(x)=x4+x3+x+1=(x+1)2(x2+x+1)f(x)=x+1

或

f(x)=x2+x+1线性递推式：at=at-4+at-3+at-1逻辑框图为：P141定理6.4x4x3x2x1x1x2x3x4c1c2c3c4c1c2c3c4x1x2x3x4f(x)=x4+x3+x+1=(x+1)2(x2+x+1)初始序列：0001

01100010010111110000x1x2x3x4f(x)=x4+x3+x+1=(x+1)2(x2+x+1)输出序列：000111//000111//……

周期为6

011//011//……

周期为3

001//001//……周期为3

01//01//……周期为2

111111…..周期为1

000000……周期为16.6线性移位寄存器序列极小多项式定理6.5设a∞

是GF(q)上的一个周期序列,则一定存在唯一的一元多项式m(x),使得a∞

∈G(m),并且对任意满足的一元多项式f(x)，都有m(x)|f(x).这里m(x)和f(x)都是GF(q)上的常数项为1的一元多项式6.6线性移位寄存器序列极小多项式定义6.4设是GF(q)上的一个周期序列,令

I中次数最低的多项式称为

的极小多项式定义6.5设，并且常数项不为0，满足的最小正整数r称为一元多项式f(x)的周期,记为p(f(x)).

例子：f(x)=x4+x3+x2+x+1的周期为p(f)=r=5

(x4+x3+x2+x+1)(1-x)=1-x5例子：f(x)=x4+x3+x2+x+1的周期为p(f)=r=5

(x4+x3+x2+x+1)(1-x)=1-x5x4x3x2x1第7时刻1000第0时刻0011第1时刻0001第2时刻1000第3时刻1100第4时刻0110第5时刻0011第6时刻0001x4x3x2x1第7时刻0001第0时刻0110第1时刻0011第2时刻0001第3时刻1000第4时刻1100第5时刻0110第6时刻0011例子：f(x)=x4+x3+x2+x+1的周期为p(f)=r=5

(x4+x3+x2+x+1)(1-x)=1-x5定理6.6：设f(x)

Fq[x]并且常数项不为0，，则f(x)的周期存在并且P(f(x))≤qn-1P145定理6.7：设a∞是GF(q)上的一个周期序列，m(x)为a∞的极小多项式，则P(a∞)=P(m(x))P146P139定义6.2定义6.7本原多项式设f(x)

Fq[x]并且常数项不为0，若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。以本原多项式为连接多项式产生的非零序列均是m序列。P147定理6.8：设f(x)是GF(q)上的并且常数项为1的一元多项式，a∞是以f(x)为联系多项式的线性移位寄存器的非零输出序列。如果f(x)是不可约的，则f(x)是a∞的极小多项式。P147定理6.9：设f(x)是GF(q)上的并且常数项为1的一元多项式，。如果任意非零输出序列a∞都是m序列。则f(x)是不可约的。6.6线性移位寄存器序列极小多项式定理6.5设是GF(q)上的一个周期序列,则一定存在唯一的一元多项式m(x),使得

∈G(m),并且对任意满足的一元多项式f(x)，都有m(x)|f(x).这里m(x)和f(x)都是GF(q)上的常数项为1的一元多项式6.6线性移位寄存器序列极小多项式定理6.6设，并且常数项不为0，则f(x)的周期存在并且定理6.7设是GF(q)上的一个周期序列,为

的极小多项式,则6.6线性移位寄存器序列极小多项式定理6.8设f(x)是上的常数项为1的一元多项式,

是以f(x)为联系多项式的线性移位寄存器的非零输出序列。如果f(x)是不可约的,则f(x)是的极小多项式。定理6.9设f(x)是上的常数项为1的一元多项式,。如果任意非零序列都是m序列,即则f(x)一定是不可约的。6.6线性移位寄存器序列极小多项式定理6.10设f(x)是上的常数项为1的一元多项式,。则任意非零序列，都是m序列,即当且仅当f(x)是本原多项式。6.7m序列的伪随机性6.7

m序列的伪随机性GF(2)上的随机序列的一般特性1.分布特性对任意的

都有2.相关特性对任意的有3.游程特性对任意的i≥0,k≥1,有点击查看GF(2)

上伪随机序列的性质若干个信号连续出现的现象称游程。对于序列a∞，称a∞中形如01…10或10…01的段为一个1游程或0游程，游程中所含1或0的个数称为该游程的长度，如0110为一个长为2的1游程，101为一个长为1的0游程。定义6.8自相关函数若a∞=(a0a1a2a3…)是GF(2)上的一个周期为T的序列，定义序列a∞的自相关函数为:P149定理6.11设a∞=(a0a1a2a3…)是GF(2)上的一个周期为T的序列性质1

：n阶m序列的一个周期中，1出现2n-1

个，0出现2n-1-1个。将a∞的一个周期排成一个圈，如右图所示：a0a1a2a3

性质3：若a∞的自相关函数为：

性质2：在n级m序列的一个周期中，游程总数为2n-1

；长度为i(1≤I≤n-2)

的1游程和0游程各有2n-i-2

个，有1个长度为n的1游程，

没有长度为n的0游程和1个长度为n-1的0游程，没有长度为n-1的1游程。P151-152（P152证)6.8

B-M算法与序列的线性复杂度上节内容复习移位寄存器序列的三种表示方法：线性递推式（一元多项式）：

at+n=c1at+n-1+c2at+n-2+…+cnat,t>=0联结多项式：

f(x)=1+c1x+c2x2+…+cnxn状态转移矩阵：满足：st+1=stTf

称st=(at,at+1,at+2,…,at+n-1)为n维状态p153

根据密码学的需要，对线性反馈移位寄存器(LFSR:（LinearFeedbackShiftingRegister)主要考虑下面两个问题：（1）如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列，即固定级数时，什么样的移存器序列周期最长。这是从密钥生成角度考虑，用最小的代价产生尽可能好的、参与密码变换的序列。

（2）当已知一个长为N序列a∞时，如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。如果f(x)是一个能产生a∞并且级数最小的线性移位寄存器的反馈多项式，l是该移存器的级数，则称<f(x),l>为序列a∞的线性综合解。1、B-M算法概念简介设a∞=(a0a1a2a3…an)是F2上的长度为n的序列，而f(x)=c0+c1x+c2x2+…+clxl是F2上的多项式，c0=1。如果序列中的元素满足递推关系：

则称<f(x),l>产生二元序列a∞。其中<f(x),l>表示以f(x)为反馈多项式的l级

线性移位寄存器。

线性移位寄存器的综合问题可表述为：给定一个n长二元序列a∞，如何求出产生这一序列的最小级数的线性移位寄存器，即最短的线性移存器？几点说明：1、反馈多项式f(x)的次数l。因为产生a∞且级数最小的线性移位寄存器可能是退化的，在这种情况下f(x)的次数<l；并且此时

f(x)中的cl=0，因此在反馈多项式f(x)中c0=1，但不要求cl=1。2、规定：0级线性移位寄存器是以f(x)=1为反馈多项式的线性移位寄存器，且n长(n=1,2,…,N)全零序列，仅由0级线性移位寄存器产生。事实上，以f(x)=1为反馈多项式的递归关系式是：ak=0，k=0,1,…,n-1.因此，这一规定是合理的。3、给定一个N长二元序列a∞，求能产生a∞并且级数最小的线性移位寄存器，就是求a∞的线性综合解。利用B-M算法可以有效的求出。2、B-M算法要点用归纳法求出一系列线性移位寄存器：<fn(x),ln>每一个<fn(x),ln>都是产生序列a∞的前n项的最短线性移位寄存器，在<fn(x),ln>的基础上构造相应的<fn+1(x),ln+1>，使得<fn+1(x),ln+1>是产生给定序列前n+1项的最短移存器，则最后得到的<fN(x),lN>就是产生给定N长二元序列a∞的最短的线性移位寄存器。任意给定一个N长序列a∞=(a0a1a2a3…aN-1)，按n归纳定义<fn(x),ln>,n=0,1,2,…,N-1。1、取初始值：

f0(x)=1，l0=0。2、设<f0(x),l0>,<f1(x),l1>,…,<fn(x),ln>,(0≤n≤N)均已求得，且l0

≤l1

≤…≤ln3、B-M算法记：再计算：称dn为第n步差值。然后分两种情形讨论：最后得到的<fN(x),lN>,便是产生序列a∞的最短线性移位寄存器。53B-M算法流程例2、设a(10)=0001101111是二元域GF(2)上的一个长度为10的序列，求其线性综合解。4、实例(1)(1)

由

n0=3得d0=d1=d2=0,dn0=d3=an0=a3=1；f1(x)=f2(x)=f3(x)=1,fn0+1(x)=

f4(x)=1-dn0xn0+1=1-d3x3+1=1-x3+1=1-x4,l0=l1=l2=∙∙∙=ln0=0即：

l0=l1=l2=l3=0，ln0+1=l3+1=l4=n0+1=3+1=4解：设a0a1a2a3a4

a5a6a7a8a9

=0001101111

，取初值f0(x)=1,l0=0(2)根据前面已经计算出的：

f4(x)=1-x4,l4=4

计算d4：fn(x)=1+c1x+c1x+c2x2+

∙∙∙+clxl(l4=4)

f4(x)=1+c1x+c2x2+

c3x3+c4x4

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d4=a4+0·a3+0·a2+0·a1-1·a0=1

<c由1-x4,来决定的>a0a1a2a3a4

a5a6a7a8a9

=0001101111

因为

l3=0,l4=4，l3<l4，故n=4，m=3，由此:<P154假设2,d4=1≠0>

f5(x)=f4(x)+d4d3-1x4-3f3(x)=f4(x)+xf3(x)=1+x-x4l5=max{4,4+1-4}=max{4,1}=4(3)根据前面已经计算出的：

f5(x)=1+x-x4,l5=4

计算d5：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f5(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d5=a5+1·a4+0·a3

+0·a2

-1·a1=1，(没有a0)a0a1a2a3a4

a5a6a7a8a9

=0001101111

因为

l3<l4=l5

=4

，这时n=5，m=3，从而

<P154假设2,d5=1≠0>

f6(x)=f5(x)+d5d3-1x5-3f3(x)=1+x+x2-x4

l6=max{4,5+1-4}=max{4,2}=4(4)根据前面已经计算出的：

f6(x)=1+x+x2-x4,l6=4计算d6：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f6(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5和x6)dn=an+c1·an-1+c2·an-2+…+cl·an-ld6=a6+1·a5+1·a4

+0·a3-1·a2=1+1=0，(没有a1和a0)a0a1a2a3a4

a5a6a7a8a9

=0001101111

因为

l3<l4=l5=l6

=4

，这时n=6，m=3，从而

<P154假设1,d6=0>

fn+1(x)=fn(x),f7(x)=f6(x)=1+x+x2-x4ln+1=ln,l7=l6=4a0a1a2a3a4

a5a6a7a8a9

=0001101111

(5)根据前面已经计算出的：

f7(x)=1+x+x2-x4,l7=4

计算d7：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f7(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5,x6,x7)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d7=a7+1·a6+1·a5+0·a4-1·a3=1+1-1=1，(没有a2,a1,a0)因为

l3<l4=l5=l6=l7

=4

，这时n=7，m=3，从而<P154假设2,d7=1≠0>

f8(x)=f7(x)+d7d3-1x7-3f3(x)=1+x+x2

l8=max{4,7+1-4}=max{4,4}=4(6)根据前面已经计算出的：

f8(x)=1+x+x2

,l8=4

计算d8：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f8(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5,x6,x7

,x8)dn=an+c1·an-1+c2·an-2+…+cl·an-l

d8=a8+1·a7

+1·a6+0·a5+0·a4=1+1+1=1，因为

l3<l4=l5=l6=l7=l8

=4

，这时n=8，m=3，从而

<P154假设2,d8=1≠0>

f9(x)=f8(x)+d8d3-1x8-3f3(x)=1+x+x2+x5

l9=max{4,8+1-4}=max{4,5}=5a0a1a2a3a4

a5a6a7a8a9

=0001101111

(10)根据前面已经计算出的：

f9(x)=1+x+x2+x5

,l9=5

计算d9：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=5)

f8(x)=1+c1x+c2x2+

c3x3+c4x4+c5x5

(没有

x6,x7,x8,x9)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d9=a9+1·a8

+1·a7

+0·a6+0·a5+1·a4=1+1+1+1=0，这表明，<1+x+x2+x5,5>即为产生所给序列一个周期的最短线性移位寄存器。因为

l4=l5=l6=l7=l8=4

,

l9=5

，

l4<

l9

，这时n=9，m=8，从而

<P154假设1,d9=0>

f10(x)=f9(x)=1+x+x2+x5

l10=l9=5a4a3a2

a1a0x1x2x3x4验证：

<1+x+x2+x5,5>是产生该a0a1a2a3a4

a5a6a7a8a9

=0001101111

序列的最短线性移位寄存器。x5c1c2c3c4c5f(x)=1+x+x2+x5f(x)=x1+x4+x5an=an-1+an-2+an-5第0时刻11000第1时刻0

110

0第2时刻1

0

1

1

0第3时刻1

1

0

1

1第4时刻1

1

1

0

1

第5时刻1

1

1

1

0

a4a3a2

a1a0x1x2x3x4x5a0a1a2a3a4

a5a6a7a8a9

=0001101111

第6时刻0

1

1

1

1第7时刻0

0

1

1

1第8时刻1

0

0

1

1第9时刻

0

1

0

0

1第10时刻0

0

1

0

02、实例(2)例2、设a(7)=

0011101是二元域GF(2)上的一个长度为7的序列，求其线性综合解。4、实例(2)解：设a0a1a2a3a4

a5a6=

0011101

，取初值f0(x)=1,l0=0(1)

由

n0=2得d0=d1=0,dn0=d2=an0=a2=1；p153f1(x)=f2(x)=1,fn0+1(x)=

f3(x)=1-dn0xn0+1=1-d2x2+1=1-x2+1=1-x3,l0=l1=l2=∙∙∙=ln0=0即：

l0=l1=l2=0，ln0+1=l2+1=l3=n0+1=2+1=3(2)根据前面已经计算出的：f3(x)=1-x3,

l3=3

计算d3：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(l3=3)

f3(x)=1+c1x+c2x2+

c3x3

dn=an+c1·an-1+c2·an-2+…+cl·an-l

(l3=3)

d3=a3+0·a2+0·a1

-1·a0=1因为l2=0，

l3=3，

l2<l3

，从而n=3，m=2，从而:<P154假设2,d3=1≠0>f4(x)=f3(x)+d3d2-1x3-2f2(x)=f3(x)+x3-2f2(x)=1+x-x3l4=max{3,3+1-3}=max{3,1}=3a0a1a2a3a4

a5a6=

0011101

(3)根据前面已经计算出的：

f4(x)=1+x-x3,

l4=3

计算d4：

fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(l4=3)

f4(x)=1+c1x+c2x2+

c3x3

dn=an+c1·an-1

+c2·an-2

+…+cl·an-l(l4=3)

d4=a4+1·a3+0·a2

-1·a1=1+1=0,<c由1+x-x3,来决定的>因为l2=0，

l2<l3=l4=3，从而n=4，m=2，从而:<P154假设1,d4=0>

f5(x)=f4(x)=1+x-x3

l5=l4=3a0a1a2a3a4

a5a6=

0011101

(4)根据前面已经计算出的：

f5(x)=1+x-x3,

l5=3

计算d5：

fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(l5=3)

f5(x)=1+c1x+c2x2+

c3x3

dn=an+c1·an-1+c2·an-2+…+cl·an-l(l5=3)

d5=a5+1·a4+0·a3

-1·a2=1-1=0，<c由1+x-x3,来决定的>因为l2=0，

l2<l3=l4=l5=3，从而n=5，m=2，从而:<P154假设1,d5=0>从而

f6(x)=f5(x)=1+x-x3

l6=l5=3a0a1a2a3a4

a5a6=

0011101

(7)根据前面已经计算出的：

f6(x)=1+x-x3,

l6=3

计算d6：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(l6=3)

f6(x)=1+c1x+c2x2+

c3x3

dn=an+c1·an-1+c2·an-2+…+cl·an-l(l6=3)

d6=1·a6+1·a5+0·a4-1·a3=1-1=0，<c由1+x-x3,来决定的>因为l2=0，

l2<l3=l4=l5=l6=3，从而n=6，m=2，从而:<P154假设1,d6=0>从而

f7(x)=f6(x)=1+x-x3

l7=l6=3这表明，<1+x-x3,3>即为产生所给序列一个周期的最短线性移位寄存器。

a0a1a2a3a4

a5a6=

0011101

a2a1

a0c1c2c3x1x2x3验证：<1+x-x3,3>是产生该序列的最短线性移位寄存器。a0a1a2a3a4

a5a6=

0011101

f(x)=1+x-x3an=an-1+an-3a2a1

a0c1c2c3x1x2x3第0时刻100a0a1a2a3a4

a5a6=

0011101

第1时刻110第2时刻111第3时刻011第4时刻101第5时刻010第6时刻001第7时刻100第8时刻110讨论：P153最后一行公式

fn0+1(x)=1-dn0xn0+1fn0+1(x)=1+dn0xn0+1对移位寄存器的构造的影响？3、实例(3)例2、求产生周期为7的m序列一个周期：0011101的最短线性移位寄存器。4、实例(3)由实例（2）变形(1)

由

a0=0得d0=1•a0=0从而f1(x)=1,l1=0；(3)由a2=1得d2=1•a2=1，从而根据l0=l1=l2=0知

f3(x)=1+d2x2+1=1+x2+1=1+x3,l3=3p153(2)同理由a1=0得d1=1•a1=0从而f2(x)=1,l2=0。解：设a0a1a2a3a4

a5a6=

0011101

，取初值f0(x)=1,l0=0(4)根据前面已经计算出的：f3(x)=1+x3,l3=3P154假设2

计算d3：dn=an+c1·an-1+c2·an-2+…+cl·an-l(l3=3)

d3=a3+0·a2+0·a1+1·a0=1因为

l2<l3，故n=3，m=2，由此:f4(x)=f3(x)+d3d2-1x3-2f2(x)=f3(x)+x3-2f2(x)=1+x+x3l4=max{3,3+1-3}=max{3,1}=3(5)计算d4：dn=an+c1·an-1

+c2·an-2

+…+cl·an-l(l4=3)d4=a4+1·a3+0·a2+1·a1=0,从而f5(x)=f4(x)=1+x+x3

l5=l4=3P154a0a1a2a3a4

a5a6=

0011101

(6)计算d5：d5=a5+1·a4+0·a3+1·a2=0，从而

f6(x)=f5(x)=1+x+x3

l6=l5=3(7)计算d6：d6=1·a6+1·a5+0·a4+1·a3=0，从而

f7(x)=f6(x)=1+x+x3

l7=l6=3这表明，<1+x+x3,3>即为产生所给序列一个周期的最短线性移位寄存器。a0a1a2a3a4

a5a6=

0011101

4、实例(4)例4、设a(11)=

00100011101

是二元域GF(2)上的一个长度为11的序列，求其线性综合解。4、实例(4)解：设a0a1a2a3a4

a5a6a7a8a9a10=

00100011101，取初值f0(x)=1,l0=0(1)

由

n0=2得d0=d1=0,dn0=d2=an0=a2=1；p153f1(x)=f2(x)=1,fn0+1(x)=

f3(x)=1-dn0xn0+1=1-d2x2+1=1-x2+1=1-x3,l0=l1=l2=∙∙∙=ln0=0即：

l0=l1=l2=0，ln0+1=l2+1=l3=n0+1=2+1=3(2)根据前面已经计算出的：

f3(x)=1-x3,l3=3

计算d4：fn(x)=1+c1x+c1x+c2x2+

∙∙∙+clxl(l3=3)

f3(x)=1+c1x+c2x2+

c3x3

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d3=a3+0·a2+0·a1-1·a0=0+0+0-0=0

<c由1-x3,来决定的>

因为

l2=0,l3=3，

l2<l3

，故n=3，m=2，由此:<P154假设1,d3=0>

fn+1(x)=fn(x),f4(x)=f3(x)=1-x3

ln+1=ln

,l4=l3=3012345678910a0a1a2a3a4

a5a6a7a8a9a10

=00100011101(3)根据前面已经计算出的：

f4(x)=1-x3,l4=3

计算d4：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=3)

f4(x)=1+c1x+c2x2+

c3x3

(没有x4)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d4=a4

+0·a3+0·a2

-1·a1=0+0+0-0=0，(没有a0)

因为

l2<l3=l4

=3

，这时n=4，m=2，从而

<P154假设1,d4=0>

f5(x)=

f4(x)=1-x3

l5=l4=3012345678910a0a1a2a3a4

a5a6a7a8a9a10

=00100011101(4)根据前面已经计算出的：

f5(x)=1-x3,l5=3

计算d5：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=3)

f5(x)=1+c1x+c2x2+

c3x3

(没有x5)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d5=a5+0·a4

+0·a3

-1·a2=0+0+0-1=1，(没有a0a1)

因为

l2<l3=l4

=l5

=3

，这时n=5，m=2，从而<P154假设2,d5=1≠0>

f6(x)=

f5(x)+d5d2-1x5-2f2(x)=1-x3+x3=1

l6=max{3,5+1-3}=max{3,3}=3012345678910a0a1a2a3a4

a5a6a7a8a9a10

=

00100011101(5)根据前面已经计算出的：

f6(x)=1

,l6=3计算d6：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=3)

f6(x)=1+c1x+c2x2+

c3x3

(没有x4x5和x6)dn=an+c1·an-1+c2·an-2+…+cl·an-l

d6=a6+1·a5+1·a4+-1·a3=1+0+0-0=1，

因为

l2<l3=l4=l5=l6

=3

，这时n=6，m=2，从而

<P154假设2,d6≠0>

f7(x)=f6(x)+d6d2-1x6-2f2(x)=1+x4.(1)=1+

x4

l7=max{3,6+1-3}=max{3,4}=4012345678910a0a1a2a3a4

a5a6a7a8a9a10

=

00100011101(6)根据前面已经计算出的：

f7(x)=1+x4

,l7=4

计算d7：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f7(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5,x6,x7)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d7=a7+0·a6+0·a5+0·a4+1·a3=1+0+0+0+0=1因为l6

=3,l7

=4,

l6

<l7

，这时n=7，m=6，从而<P154假设2,d7=1≠0>

f8(x)=

f7(x)+d7d6-1x7-6f6(x)=1

+x+x4

l8=max{4,7+1-4}=max{4,4}=4012345678910a0a1a2a3a4

a5a6a7a8a9a10

=

00100011101(7)根据前面已经计算出的：

f8(x)=1+x+x4

,l8=4

计算d8：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f8(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5,x6,x7

,x8)dn=an+c1·an-1+c2·an-2+…+cl·an-l

d8=a8+1·a7

+0·a6+0·a5+1·a4=1+1+0+0+0=0，因为

l6<l7

=l8

=4

，这时n=8，m=6，从而

<P154假设2,d8=0>

f9(x)=

f8(x)=1+x+x4

l9=l8=4012345678910a0a1a2a3a4

a5a6a7a8a9a10

=

00100011101(8)根据前面已经计算出的：

f9(x)=1+x+x4

,l9=4

计算d9：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l=4)

f9(x)=1+c1x+c2x2+

c3x3+c4x4

(没有x5

x6,x7,x8,x9)

dn=an+c1·an-1+c2·an-2+…+cl·an-l

d9=a9+1·a8

+0·a7

+0·a6+1·a5=0+1+0+0+0=1，因为

l6

=3,l7

=l8=l9=4

，

l6<

l9

，这时n=9，m=6，从而

<P154假设2,d9≠0>

f10(x)=f9(x)+d9d6-1x9-6f6(x)=1

+x+x3+x4

l10=max{4,9+1-4}=max{4,6}=6

012345678910a0a1a2a3a4

a5a6a7a8a9a10

=

00100011101(9)根据前面已经计算出的：

f10(x)=1+x+x3+x4

,l10=6

计算d10：fn(x)=1+c1x+c1x+c2x2+∙∙∙+clxl(这时l