現代密碼學第6章 序列密碼與移位寄存器

主要內容序列密碼的基本原理移位寄存器與移位寄存器序列線性移位寄存器的表示線性移位寄存器序列的周期性線性移位寄存器的序列空間線性移位寄存器序列的極小多項式m序列的偽隨機性B-M算法與序列的線性復雜度線性移位寄存器的非線性組合第6章序列密碼與移位寄存器6.1序列密碼的基本原理

由少量的隨機密鑰,通過移位寄存器以及非線性變換等多層編碼環(huán)節(jié)，產生變化量大、復雜度高、隨機性好的偽隨機亂數，利用簡單的密碼法把它與明文數據串進行結合，從而實現對明文數據的加密。高杏欣: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ài)t+1

時狀態(tài)反饋移位寄存器序列反饋移位寄存器的狀態(tài)序列,點此查看定義6.1一、線性反饋移存器簡介（一）基本概念

定義：反饋移存器的反饋邏輯電路可用一布爾函數來表示，若對應的布爾函數是線性函數，則稱該反饋移存器為線性反饋移存器，否則稱為非線性反饋移存器。P136定義6.11342123圖1、線性反饋移位寄存器圖2、非線性反饋移位寄存器圖中存在與門器件，所以是非線性。（二）、工作原理假設在j時刻其內部狀態(tài)為：在j+1時刻其內部狀態(tài)變?yōu)椋浩渲校捍藭r的輸出為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

聯(lián)結多項式：

f(x)=1+c1x+c2x2+…+cnxn狀態(tài)轉移矩陣：滿足：st+1=stTf

稱st=(at,at+1,at+2,…,at+n-1)為n維狀態(tài)實例（寫出相應的線性遞推式，畫出移存器的邏輯框圖）多項式

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：聯(lián)結多項式為

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)為聯(lián)系多項式的線性移位寄存器的非零輸出序列。如果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)為聯(lián)系多項式的線性移位寄存器的非零輸出序列。如果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)

上偽隨機序列的性質若干個信號連續(xù)出現的現象稱游程。對于序列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算法與序列的線性復雜度上節(jié)內容復習移位寄存器序列的三種表示方法：線性遞推式（一元多項式）：

at+n=c1at+n-1+c2at+n-2+…+cnat,t>=0聯(lián)結多項式：

f(x)=1+c1x+c2x2+…+cnxn狀態(tài)轉移矩陣：滿足：st+1=stTf

稱st=(at,at+1,at+2,…,at+n-1)為n維狀態(tài)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、規(guī)定：0級線性移位寄存器是以f(x)=1為反饋多項式的線性移位寄存器，且n長(n=1,2,…,N)全零序列，僅由0級線性移位寄存器產生。事實上，以f(x)=1為反饋多項式的遞歸關系式是：ak=0，k=0,1,…,n-1.因此，這一規(guī)定是合理的。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