幾類偽隨機序列的研究_圖文

1、分類號口翌密級編號中國科學(xué)院研究生院博士學(xué)位論文且耋魚瞳扭壓到鮑嬰窒塑塹塑指導(dǎo)教師墨登國熬援蟲國科堂睦班囂生睫值星塞全墾塞重盛塞墜窒申請學(xué)位級別煎±學(xué)科專業(yè)名稱通籃生信息丕纏論文提交日期§璽旦論文答辯日期螻生旦旦培養(yǎng)單位蟲國整堂瞳嬰筮生睦生墾揖堂隧壘王堂硒冠壓學(xué)位授予單位史國抖堂隧亞塑生醫(yī)答辯委員會主席墓盍厶瞳圭摘要偽隨機序列在密碼學(xué)、擴頻通信、計算、控制等領(lǐng)域都有廣泛的應(yīng)用。偽隨機序列的設(shè)計和分析一直是國際上的研究熱點，尋找新的方法來設(shè)計更多性質(zhì)良好的序列，以及尋找更有力的工具來分析清楚已有序列的性質(zhì)，都是非常有價值的工作。在本文中，我們對偽隨機序列中的幾個問題進行了深入

2、的研究，這些問題是：帶進位的反饋移位寄存器（）、二元序列的復(fù)雜度、周期序列的廣義離散傅立葉變換和周期序列的一線性復(fù)雜度、兩類邑導(dǎo)出序列的獨立一樣式分布和部分周期性質(zhì)、利用函數(shù)域設(shè)計序列等等。具體地說主要貢獻如下：）給出了序列分布的明顯公式，利用這個公式討論了序列的游程分布等分布性質(zhì)。討論了序列的通常自相關(guān)和算術(shù)自相關(guān)。證明了二元序列在某些條件下具有大的和線性復(fù)雜度。）指出了二元周期序列線性復(fù)雜度和復(fù)雜度的一個顯著的差別，討論了這個差別對序列綜合的影響?；谶@一觀察，給出了更加合理的二元周期序列對稱復(fù)雜度的概念。計算了二元周期序列復(fù)雜度和對稱復(fù)雜度的期望值。給出了二元周期序列復(fù)雜度和對稱復(fù)雜度的

3、非平凡下界。）指出上年和年的兩篇論文的結(jié)果本質(zhì)上是一祥的。）將周期序列的廣義離散傅立葉變換應(yīng)用到周期序列的線性復(fù)雜度的研究中去，構(gòu)造了許多具有大的線性復(fù)雜度的序列，改進了的結(jié)果。）利用環(huán)上的指數(shù)和估計分析了兩類磊導(dǎo)出序列的獨立一樣式分布，證明了它們都是漸進均勻的，所得結(jié)果改進了以前的公開結(jié)果。）利用環(huán)上的混合指數(shù)和估計與離散傅立葉變換，給出了環(huán)上的部分指數(shù)和估計。）利用環(huán)上的部分指數(shù)和估計，分析了兩類邑導(dǎo)出序列的部分周期分布和部分周期獨立一樣式分布，證明了它們也都是漸進均勻的。摘要）利用函數(shù)域的擴張構(gòu)造了一類新的具有低相關(guān)和高線性復(fù)雜度的二元周期序列，并且使用橢圓函數(shù)域的理論給出了一些具體例子

4、。在某些情況下，我們的構(gòu)造方法比等學(xué)者的構(gòu)造方法更好，關(guān)鍵詞線性復(fù)雜度，線性復(fù)雜度，復(fù)雜度，復(fù)雜度，環(huán)上的指數(shù)和，環(huán)上的部分指數(shù)和，周期序列的一樣式，函數(shù)域，函數(shù)域的擴張。（），：（），一，揚，：），），），邑），¨），：，研究成果聲明本人鄭重聲明：所提交的學(xué)位論文是我本人在指導(dǎo)教師的指導(dǎo)下進行的研究工作獲得的研究成果。盡我所知，文中除特別標(biāo)注和致謝的地方外，學(xué)位論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得中國科學(xué)院電子學(xué)研究所或其它教育機構(gòu)的學(xué)位或證書所使用過的材料。與我一同工作的合作者對此研究工作所做的任何貢獻均已在學(xué)位論文中作了明確的說明并表示了謝意。特此申明。

5、簽名：鍋幼習(xí)日期：神關(guān)于學(xué)位論文使用權(quán)的說明本人完全了解中國科學(xué)院電子學(xué)研究所有關(guān)保留、使用學(xué)位論文的規(guī)定，其中包括：電子所有權(quán)保管、并向有關(guān)部門送交學(xué)位論文的原件與復(fù)印件；電子所可以采用影印、縮印或其它復(fù)制手段復(fù)制并保存學(xué)位論文；電子所可允許學(xué)位論文被查閱或借閱；電子所可以學(xué)術(shù)交流為目的，復(fù)制贈送和交換學(xué)位論文；電子所可以公布學(xué)位論文的全部或部分內(nèi)容（保密學(xué)位論文在解密后遵守此規(guī)定）。簽名：鑰譬）羽日期：矽日期：礦導(dǎo)師簽名：。，設(shè)曩第一章緒論§研究背景和意義隨著計算機和通信網(wǎng)絡(luò)的廣泛應(yīng)用，信息安全越來越受到人們的重視，在年發(fā)表了著名論文“保密通信的信息理論”，這是密碼年，、和提出了

6、著名的算法。同當(dāng)今的密碼體制根據(jù)密鑰的特點可以分為對稱密碼體制和非對稱密碼，小是明文比特流，覷，是密鑰比特流，：，是密文比特流，。鬼序列密碼加解密實現(xiàn)方式簡單，速度快，而且理論相對比較成熟（一個而密碼技術(shù)是保證信息的安全性的關(guān)鍵技術(shù)。隨著社會的進一步發(fā)展，密碼技術(shù)將得到更加廣泛的應(yīng)用，這將為密碼學(xué)的發(fā)展提供更加廣闊的舞臺。學(xué)由一門藝術(shù)成為一門科學(xué)的標(biāo)志。到了上個世紀(jì)年代，人類開始進入信息時代，密碼學(xué)也進入了快速發(fā)展的時期。年，和發(fā)表了“密碼學(xué)的新方向”，提出了公鑰密碼體制，使密碼學(xué)經(jīng)歷了一場變革。年，美國公布了由公司研制的數(shù)據(jù)加密標(biāo)準(zhǔn)（）。從此以后，密碼學(xué)不再局限于政治和軍事，其商用價值和社會

7、價值得到充分肯定。大量的密碼學(xué)論文開始出現(xiàn)，許多有關(guān)信息安全的工業(yè)標(biāo)準(zhǔn)被公布，進入這一領(lǐng)域的公司和大學(xué)也越來越多體制。在對稱密碼體制中，加密密鑰和解密密鑰相同，或者從一個容易得到另一個。然而在非對稱密碼體制中，加密密鑰和解密密鑰不同，從一個很難得到另一個，加密和解密是可分離的按照具體實現(xiàn)方式對稱密碼體制又可分為序列密碼和分組密碼兩種基本方式。在序列密碼體制中，加密時將明文消息字符流逐位地加密成密文消息字符流，解密時則將密文消息字符流逐位地解密成明文消息字符流。下面用二元時的例子來說明。設(shè)那么相應(yīng)的加解密變換是重要原因是數(shù)學(xué)這一工具可以有效地用來研究它），因而受到廣泛重視。序第一章緒論列密碼算法

8、的安全強度取決于相應(yīng)的密鑰流的質(zhì)量，因而產(chǎn)生好的密鑰流是序列密碼體制的關(guān)鍵問題。：證明了如果密鑰流序列是真隨機的，那么相應(yīng)的序列密碼體制將是完善保密的。通常有下面幾種方式來產(chǎn)生真隨機序列：使用隨機噪聲、使用計算機時鐘、測量鍵盤反應(yīng)時間等等。真正隨機的序列是不能重復(fù)產(chǎn)生的，即使你用相同的輸入對序列發(fā)生器操作兩次，你將得到兩條完全不同的序列。在一般的應(yīng)用環(huán)境中生成和使用真隨機序列是不現(xiàn)實的，因此人們便退而使用偽隨機序列做為密鑰流，于是如何產(chǎn)生和評價偽隨機序列便成為序列密碼的一個非常重要的問題。在密碼學(xué)的其它領(lǐng)域，偽隨機序列也被廣泛使用，比如著名的和數(shù)字簽名算法這兩個數(shù)字簽名算法分別基于有限域上的離

9、散對數(shù)和橢圓曲線上的離散對數(shù)這兩個困難問題，在簽名過程中需要使用偽隨機數(shù)。雖然求解有限域和橢圓曲線上的離散對數(shù)都是困難的，但是如果簽名過程中使用的偽隨機數(shù)不安全，這兩個簽名算法將很容易被攻擊。偽隨機序列在擴頻通信中也有重要應(yīng)用。從上個世紀(jì)年代開始，數(shù)字無線通信開始成為主流，實際的系統(tǒng)有等。由于無線信道是開放的，通信環(huán)境很容易受到各種干擾，使得信號傳輸?shù)目煽啃越档?。另一方面，無線業(yè)務(wù)的快速增長要求無線網(wǎng)絡(luò)具有高度的靈活性，以逶應(yīng)業(yè)務(wù)的發(fā)展變化。這些都是傳統(tǒng)的無線通信系統(tǒng)無法解決的。擴頻通信將待傳輸?shù)男盘栍脗坞S機序列調(diào)制，實現(xiàn)頻譜擴展后再傳輸，很好地解決了上面的可題。擴頻時使用的偽隨機序列，要求具

10、有低的非平凡自相關(guān)和互相關(guān)，這保證了同步相關(guān)的輸出遠(yuǎn)遠(yuǎn)大于非同步相關(guān)的輸出，大大降低了信號之間的干擾。在擴頻通信中，所有用戶可以共用同一頻帶，簡化了系統(tǒng)的設(shè)計，提高了靈活性。而們已經(jīng)知道了它們的許多性質(zhì)，但仍然有更多的秘密不為人知，這需要更加此外，偽隨機序列在編碼、計算、控制等領(lǐng)域中也有廣泛的應(yīng)用。從上面的討論可以看出，偽隨機序列不是一個孤立的問題，它與數(shù)學(xué)、且擴頻通信還具有保密、高精度測量等優(yōu)點。尋找擴頻時所需要的偽隨機序列是國際上眾多學(xué)者長期以來一直進行的工作。另一方面，對于現(xiàn)在已經(jīng)找到的那些偽隨機序列，分析清楚它們的各種性質(zhì)也是非常有意義的。雖然人有力的數(shù)學(xué)工具。通信、計算機等等許多領(lǐng)域

11、都有聯(lián)系，它既有很強的理論背景，也有很強的應(yīng)用背景，因此從事這方面的研究是有意義的。而且這方面的問題將一直被第一章緒論人們討論下去。一條周期序列應(yīng)該盡可能滿足以下幾個隨機性準(zhǔn)則（我們用上的序列做為例子）：）大的周期：任意確定性算法生成的序列都是周期的，要想獲得好的隨機性，周期應(yīng)該盡量大；）平衡性：比如在二元序列的一個周期段中，與的個數(shù)相羞要盡量小。一條不平衡的偽隨機序列在實際應(yīng)用中無疑會帶來安全隱患；）高的線性復(fù)雜度；一條序列的線性復(fù)雜度定義為生成該序列的最短線性反饋移位寄存器的長度。如果用表示所考慮序列的線性復(fù)雜度，使用算法，只需連續(xù)的比特就可以恢復(fù)整條序列，因此低線性復(fù)雜度的序列做為密鑰流

12、是很不安全的。）良好的統(tǒng)計特性：在文獻中，認(rèn)為對于一條偽隨機序列，在每個周期內(nèi)，它的一游程和一游程的數(shù)目基本相等。）二值自相關(guān)函數(shù)：同樣地，在文獻中，認(rèn)為對于一條偽隨機序列，它的周期自相關(guān)函數(shù)應(yīng)該是二值的。但是，在一般情況下這個要求難以達(dá)到，人們退而要求偽隨機序列的自相關(guān)函數(shù)應(yīng)該是低值的。對于有限序列，人們也提出了許多衡量其隨機性的指標(biāo)。比如：頻數(shù)、塊內(nèi)頻數(shù)、跟隨性、重疊子序列、游程變化、游程分布等等。下面我們給出兩個例子?！亢陀媚苌蛇@條序列的最短圖靈機程序的長度描述這條序列的隨機性。另一種度量有窮序列的隨機性的方法是由和提出的所謂“線性復(fù)雜度“的方法，規(guī)定用產(chǎn)生該序列的最短線性反饋移位寄存

13、器的長度來度量隨機性計算能產(chǎn)生給定序列的最短非線性反饋移位寄存器是很困難的，但是算法能夠有效地計算出產(chǎn)生給定序列的最短線性反饋移位寄存器。因此，這是一個非常實用的參數(shù)。年，和提出了一種新的產(chǎn)生偽隨機序列的移位寄存器結(jié)構(gòu)一帶進位的反饋移位寄存器（），并提出了二元序列復(fù)雜度的新的度量指標(biāo)一一復(fù)雜度。在此后的這些年中，、以及其他許多學(xué)者做了很多有關(guān)的有價值的工作。題值得我們進一步考慮。和既有許多相似之處，也有許多不同之處。有關(guān)和復(fù)雜度的問第一章緒論如果一條序列雖然具有大的線性復(fù)雜度，但是改變少量元素后會引起線性復(fù)雜度的顯著降低，那么這條序列序列用到密碼學(xué)中也是不安全的?；谶@一想法，和獨立提出了線性

14、復(fù)雜度的概念。由于這一想法的重要性，此后這個領(lǐng)域一直受到廣泛關(guān)注。直到現(xiàn)在，仍然有許多問題沒有解決。從上個世紀(jì)中葉以來，人們研究最多的是有限域上的序列。到了上個世紀(jì)年代末，環(huán)上的序列開始成為人們關(guān)注的熱點。由于環(huán)的結(jié)構(gòu)比域的結(jié)構(gòu)更復(fù)雜，因此環(huán)上的序列不但數(shù)目更多，而且密碼學(xué)性質(zhì)更好，更難于攻擊。研究環(huán)上的序列需要更深入的數(shù)學(xué)工具，而且人們研究的時間也還很短，這方面還有許多問題沒有搞清楚。尋找更多更好的擴頻序列一直是人們最求的目標(biāo)。到目前為止，人們已經(jīng)找到了許多這樣的序列，比如：序列、序列、序列、級聯(lián)序列、序列等等。等學(xué)者首次使用函數(shù)域來構(gòu)造偽隨機序列，他們使用函數(shù)域的擴張構(gòu)造了一類具有低相關(guān)和

15、高線性復(fù)雜度的二元周期序列。由于這一思想提出還不久，是否能構(gòu)造出更多的性質(zhì)好的偽隨機序列值得進一步考慮。§國內(nèi)外研究現(xiàn)狀首先我們介紹和復(fù)雜度方面的研究進展情況在文獻中，和提出了帶進位的反饋移位寄存器（）。這種移位寄存器的結(jié)構(gòu)與線性反饋移位寄存器（）的結(jié)構(gòu)很相似，主要區(qū)另是引入了記憶，分析的數(shù)學(xué)理論是數(shù)理論。的輸出序列我們稱為序列，當(dāng)序列的周期達(dá)到最大時，和將其稱為一序列。一序列是序列的算術(shù)版本。在文獻中，和將原始的推廣到了數(shù)的分歧擴張的情況，并分析了在這種情況下輸出序列的性質(zhì)?；谶@種新的，他們找到了求和發(fā)生器的明顯弱點【。在文獻】中，和系統(tǒng)地研究了一序列的性質(zhì)，比如它們的構(gòu)造和統(tǒng)計

16、性質(zhì)等等。和利用指數(shù)和估計證明了一序列在部分周期內(nèi)和的分布是漸進均勻的。和在文獻】中討論了序列的綜合問題，給第一章緒論出了有理逼近算法，該算法可以有效地找出生成給定序列的最短。后來，他們在文獻中又給出了一種的移位寄存器結(jié)構(gòu)，并在文獻中詳細(xì)分析了序列的分布特點。關(guān)于序列的線性復(fù)雜度，文獻中給出了它們的下界。關(guān)于和的具體實現(xiàn)方式，文獻中討論了兩種結(jié)構(gòu)：結(jié)構(gòu)和結(jié)構(gòu)在文獻中，和給出了周期序列算術(shù)相關(guān)的概念，并且構(gòu)造了具有理想算術(shù)互相關(guān)的大的序列簇。受到定理的啟發(fā)，、和在文獻中研究了二元周期序列的傅立葉變換和它的復(fù)雜度的關(guān)系，給出了帶進位版本的定理。竹卜序列和它們的采樣序列之間的移位等價關(guān)系是容易確定的

17、，但一序列卻要復(fù)雜很多。在文獻中，作者利用指數(shù)和估計證明了在某些情況下一序列和它的采樣序列不是移位等價的，而且作者猜想一序列和它所有的采樣序列都不是移位等價的。在文獻中，和設(shè)計了完備環(huán)上的反饋移位寄存器，這是和的共同推廣。下面我們介紹序列的線性復(fù)雜度方面的研究進展情況和獨立地提出了線性復(fù)雜度的概念。在文獻中，作者初步分析了二元序列的線性復(fù)雜度的一些性質(zhì)，并且提出了一個猜想：周期序列的線性復(fù)雜度和線性復(fù)雜度存在制約關(guān)系，它們不可能同時取得很大的值。在文獻中構(gòu)造了許多同時具有大的線性復(fù)雜度和大的線性復(fù)雜度的周期序列，從而否定了的這個猜想。文獻給出了周期為“的二元序列的線性復(fù)雜度的快速計算方法。、盯

18、和在文獻中將該算法推廣到了上周期為礦的序列的情況。文獻】討論了周期序列在一個符號替換下的線性復(fù)雜度，證明了周期序列的線性復(fù)雜度可以由該序列的極小多項式計算出來。關(guān)于一般情況下周期序列線性復(fù)雜度，文獻】給出了它們的非平凡下界對于某些特殊周期序列，幾位日本學(xué)者在文獻】中確定了最小的使得這些序列的線性復(fù)雜度嚴(yán)格小于它們的線性復(fù)雜度。對于線性復(fù)雜度這種特殊情況，文獻給出了個陜速算法計算周期為”一的二元序列的線性復(fù)雜度，并給出了幾條設(shè)計具有大的線性第一章緒論復(fù)雜度的二元周期序列的準(zhǔn)則。在文獻中，作者設(shè)計了一個快速算法計算周期序列的線性復(fù)雜度譜。該算法在文獻中被改進。和在文獻中研究了周期序列的離散傅立葉變

19、換和線性復(fù)雜度之間的關(guān)系。接著我們介紹一下環(huán)上序列的研究進展情況近多年來，環(huán)上的序列設(shè)計和分析一直是國內(nèi)外的熱點。文獻研究了邑上本原序列的最高權(quán)位序列的最小周期和極小多項式。在文獻中，作者給出了上本原序列的最高權(quán)位序列的線性復(fù)雜度的下界。在文獻中證明了具有重要密碼學(xué)價值的保墑定理。等著名學(xué)者在文獻【中給出了環(huán)版本的指數(shù)和估計，這個指數(shù)和估計對于設(shè)計和分析環(huán)上序列具有基礎(chǔ)性的作用。后來在文獻中，和在特征為的情況下改進了這類指數(shù)和。在文獻中，和他的合作者又給出了一類上的混合指數(shù)和（）估計，并利用這樣的指數(shù)和估計分析了一些環(huán)導(dǎo)出序列的非周期自相關(guān)。受到文獻】和的啟發(fā)，此后人們又給出了一些類似的環(huán)上的

20、指數(shù)和估計。在文獻【中，和利用文獻中的指數(shù)和估計分析了邑上本原序列的最高權(quán)位序列的、分布，改進了文獻中的結(jié)果。一樣式分布是有限域上周期序列的重要性質(zhì)文獻【和討論了一般環(huán)上的極大長序列的最高權(quán)位序列的獨立一樣式分布，證明了它們是漸進均勻的。在文獻】中，幾位作者研究了磊上的碼導(dǎo)出的二元序列，證明它們具有大的線性復(fù)雜度、高的非線性度和低的互相關(guān)和非平凡自相關(guān)。在文獻】中，兩位作者利用】中的方法，分析了最高權(quán)位序列的、分布，進一步改進了文獻中的結(jié)果最后我們介紹一下函數(shù)域在序列設(shè)計中的應(yīng)用情況，有限域和有限環(huán)一直是序列設(shè)計的常用方法，等學(xué)者首次將函數(shù)域引入到序列設(shè)計中來，找到了一系列性質(zhì)良好的序列。在文

21、獻】中，和設(shè)計了許多具有幾乎完美線性復(fù)雜度輪廓的序列（）。在文獻（嘲中，和他的合作者又改進了文獻】中的方法在文獻，中，進一步將這一套方法推廣到多序列的情況。等幾位學(xué)者在文獻陽中利用函數(shù)域的擴張構(gòu)第一章緒論造了一類具有低相關(guān)和高線性復(fù)雜度的二元周期序列，并且分別就有理函數(shù)域和橢圓函數(shù)域兩種情況給出了具體例子。姐本文的主要結(jié)果和章節(jié)安排在本文中，我們對偽隨機序列的設(shè)計和分析中的幾個問題進行了深入研究，主要有：帶進位的反饋移位寄存器（）和二元序列的復(fù)雜度、周期序列的廣義離散傅立葉變換和周期序列的線性復(fù)雜度、環(huán)邑導(dǎo)出序列的獨立樣式分布和部分周期性質(zhì)、函數(shù)域與序列設(shè)計等等。具體地說主要貢獻如下：）給出了

22、序列分布的明顯公式，利用這個公式討論了序列的游程分布等分布性質(zhì)。利用一般情況下序列的指數(shù)表示分析了一個周期內(nèi)元素之間的關(guān)系。討論了序列的通常自相關(guān)和算術(shù)自相關(guān)。證明了二元序列在某些條件下具有大的和線性復(fù)雜度。）指出了二元周期序列線性復(fù)雜度和復(fù)雜度的個顯著的差別，討論了這個差別對序列綜合的影響?；谶@一觀察，給出了更加合理的二元周期序列非對稱復(fù)雜度的概念。計算了二元周期序列復(fù)雜度和非對稱復(fù)雜度的期望值。給出了二元周期序列復(fù)雜度和非對稱一復(fù)雜度的非平凡下界）指出上年和年的兩篇論文的結(jié)果本質(zhì)上是一樣的。）將周期序列的廣義離散傅立葉變換應(yīng)用到周期序列的線性復(fù)雜度的研究中去，構(gòu)造了許多具有大的線性復(fù)雜度

23、的序列，改進了的結(jié)果。）利用環(huán)上的指數(shù)和估計分析了兩類邑導(dǎo)出序列的獨立。樣式分布，證明了它們都是漸進均勻的，所得結(jié)果改進了以前的公開結(jié)果。）利用環(huán)上的混合指數(shù)和估計和離散傅立葉變換，給出了環(huán)上的部分指數(shù)和估計。）利用環(huán)上的部分指數(shù)和，分析了兩類邑導(dǎo)出序列的部分周期分布和部分周期獨立一樣式分布，證明了它們也都是漸進均勻的。第一章緒論）利用函數(shù)域的擴張構(gòu)造了一類新的具有低相關(guān)和高線性復(fù)雜度的二元周期序列，并且使用橢圓函數(shù)域的理論給出了一些具體例子。在某些情況下，我們的結(jié)果比以前的公開結(jié)果更好。本文的章節(jié)安排如下：第一章（本章）介紹了研究偽隨機序列的背景和意義，以及國內(nèi)外的研究進展。第二章給出了以后

24、各章會共同用到的一些基本概念，并簡單討論了它們的性質(zhì)。第三章分析序列的統(tǒng)計性質(zhì)和線性復(fù)雜度，對二元周期序列的復(fù)雜度進行深入研究。第四章利用周期序列的廣義離散傅立葉變換研究周期序列的線性復(fù)雜度，改進了的結(jié)果。第五章對邑導(dǎo)出序列進行了深入分析。第六章利用函數(shù)域的擴張構(gòu)造一類新的具有低相關(guān)和高線性復(fù)雜度的二元周期序列，并給出了具體例子。第二章基本概念和性質(zhì)為了方便以后四章的工作，我們在這一章中給出它們會共同用到的一些基本概念，并簡要討論這些概念的一些性質(zhì)。對于以后各章單獨需要的那些概念和預(yù)備知識，我們則在各章中分別給出。§序列的周期和線性復(fù)雜度日是有個元素的有限域，其中是某個素數(shù)的方冪。本

25、章考慮的序列都是只上的。定義設(shè)（）是上一條半無限序列，如果存在正整數(shù)丁和非負(fù)整數(shù)”使得。對任意都成立，我們稱序列是終歸周期的，稱為的一個周期。序列的所有周期的最小值稱為它的最小周期，記為（）。如果他，我們稱序列是周期的。如果（）是最小周期為于的周期序列，我們也把它記為（￥）。定義（）是日上一條半無限序列，它的線性復(fù)雜度定義為滿足如下條件的最小的：是一個非負(fù)整數(shù)，存在，日，使得下面的關(guān)系成立；¨，任意的線性復(fù)雜度記為（）。需要指出的是，如果（。）是最小周期為的周期序列，那么（）。線性反饋移位寄存器（）是產(chǎn)生偽隨機序列的非常有用的裝置之一，它的一般形式如圖所示（本圖來自文獻）。記號和條件

26、同定義，多項式（）。一陋稱為序列的零化多項式。當(dāng)時，首一的零化多項式稱為特征多項式。此時多項式（），（一）第二章基本概念和性質(zhì)圖：線性反饋移位寄存器稱為序列的聯(lián)結(jié)多項式。次數(shù)最小的特征多項式稱為序列的極小多項式。因此極小多項式的次數(shù)就是生成序列的最短的線性反饋移位寄存器的長度，即序列的線性復(fù)雜度。年，給出了一個迭代算法來譯碼。兩年后，將其成功用于線性移位寄存器的綜合問題。算法可以有效地計算序列的線性復(fù)雜度，它的時間復(fù)雜度為（），空間復(fù)雜度為（）。因此，如果一條序列的線性復(fù)雜度太低，它在密碼學(xué)上是不安全的。下面介紹塌上的形式冪級數(shù)環(huán)瑪】。任意日盼中的元素（）可以表示成未定元。的形式冪級數(shù)。以扛）

27、。（。其中稱為（）的系數(shù)。日】中的兩個元素（）莖。和（）墨相等，當(dāng)且僅當(dāng)它們的所有系數(shù)相等，即，任意任意吲中的多項式尸（）十“可以看成形式冪級數(shù)（）擴”十計，于是成為【舊的子集。日中的加法和乘法定義為：！在這種規(guī)定下，：蚴枷。腳啪石瑪】形成一個整環(huán)。如果（）（。），我們稱（）和（）互為乘法逆元。第二章基本概念和性質(zhì)定理瑪盼】中的元素（）；。是乘法可逆的當(dāng)且僅當(dāng)，如果它的乘法逆元存在那么必定唯一。序列的周期與多項式的周期或階有密切的聯(lián)系，下面介紹多項式的周期及其性質(zhì)。定義設(shè)（）是日中一個次數(shù)不小于的多項式，而且（），使得廠（）（一護）成立的最小的稱為，（）的階，記為（）。如果（），那么存在整數(shù)和

28、（）矧，使得（）。夕（），我們規(guī)定（）為（）。引理，如果（）的次數(shù)，；（），那么（）（”一）。引理，設(shè)是上的一條周期序列，它的極小多項式為（），那么的最小周期等于（）。本原多項式是一類特殊的多項式，下面給出它們的定義。定義如果（）蜀的次數(shù)禮，（），如果（）曠一，那么，（）稱為本原多項式。聯(lián)結(jié)多項式為本原多項式的非零周期序列稱為一序列。一序列具有許多良好的統(tǒng)計性質(zhì)，它在密碼學(xué)和通信中有著廣泛的用途。但它也有一個明顯的缺點，那就是線性復(fù)雜度太低。對于半無限序列（），它的生成函數(shù)定義為）十銣對于有限序列，可以在它的后面添加無數(shù)個，從而將其看做無限序列。下面這個定理常常用來計算周期序列的線性復(fù)雜度和極

29、小多項式。對于某些特殊情況，可以據(jù)此設(shè)計出一蝗快速算法，。定理歸玎設(shè)（）是日上一條周期為的周期序列不必為的最小周期，它的生成函數(shù)是（），令）一那么（）表示為）辮墨！型（魚！二望（一）（島（），一丁）第二章基本概念和性質(zhì)其中（一）（曲（），一丁）是序列的極小多項式，它的線性復(fù)雜度為（）（一）（），一）一（。），一，）和獨立地提出了線性復(fù)雜度的概念，這是線性復(fù)雜度概念的自然推廣。一個密碼學(xué)強的序列不僅要有大的線性復(fù)雜度，而且改變少量位置的元素不能引起線性復(fù)雜度的顯著降低。這個領(lǐng)域的問題一直受到國際上許多學(xué)者的關(guān)注。下面給出線性復(fù)雜度的正式定義。定義副設(shè)（，）。是有限域上的一條周期為的序列，對于任意

30、，的線性復(fù)雜度，（）定義為工（），這里取遍所有周期為的序列（，）。，其中向量（，一）和（，？一）的距離不超過七，二（尸）表示的線性復(fù)雜度。在文獻】中，和給出了一個有效的算法計算周期為“的二元序列的線性復(fù)雜度后來，、和將這個算法推廣到有限域上周期為“的序列的情況。當(dāng)多大時，條序列的線性復(fù)雜度會嚴(yán)格小于它的線性復(fù)雜度，文獻在某些特殊情況下回答了這個問題。定理庳設(shè)是一條周期為“的二元序列，那么最小的使得，（）（）是（”（跏，其中（“一（）表示整數(shù)“一（）的二進制表示的重量。在文獻中作者研究了日上周期序列的線性復(fù)雜度，證明了周期序列的線性復(fù)雜度在一般情況下都能計算出來。在文獻中，作者研究了蜀上周期序列

31、在個符號替換下的線性復(fù)雜度，并給出了一般的下界，結(jié)果如下：定理設(shè)是上的一條周期為，的序列，那么一（）三（）墨第二章基本概念和性質(zhì)§序列的周期相關(guān)和非周期相關(guān)設(shè)（，）”是昂上的一條周期為的序列，它的周期自相關(guān)定義為一（）滬”，其中冬一，等，是實數(shù)域上求和。設(shè)（，）。和島（，¨，）。是上的兩條周期為的序列，它們的周期互相關(guān)定義為，。（）其中墨一，：等，是實數(shù)域上求和。設(shè)是昂上周期為的序列，它具有如下的值自相關(guān)嘶，怪葚。在通信中，我們經(jīng)常面對的其實是序列的非周期相關(guān)，因為在一般情況下，確定序列的非周期相關(guān)是一件很困難的事，所以人們轉(zhuǎn)而研究序列的周期相關(guān)，設(shè)（，）。是弓上的一條周期

32、為的序列。的非周期自相關(guān)定義為嘶）手酸墨滬一“（鬻一，鯽。其中警，是實數(shù)域上求和。容易看出（）。對任意，墨（）盯一一?。薄?，這正好是在移位處的周期自相關(guān)。關(guān)于序列的非周期自相關(guān)，有如下結(jié)果。第二章基本概念和性質(zhì)定理刪設(shè)是一條二元一序列，它的周期是，它的非周期自相關(guān)有如下的上界（）（）（）歸（），第三章序列的統(tǒng)計性質(zhì)及二元周期序列的一復(fù)雜度和在年提出了一種新的生成偽隨機序列的移位寄存器結(jié)構(gòu)，他們將其稱為帶進位的反饋移位寄存器（），并提出了二元序列復(fù)雜度的一種新的度量指標(biāo)：復(fù)雜度。在此后的一系列論文中，他們又做了許多與有關(guān)的工作。本章內(nèi)容安排如下；在第節(jié)中，介紹的概念和與之相關(guān)的基本知識；在第節(jié)

33、中，詳細(xì)分析序列的各種統(tǒng)計性質(zhì)；在第節(jié)中，分析二元序列的線性復(fù)雜度；在第節(jié)中，指出復(fù)雜度和線性復(fù)雜度的一個大的差別，基于這一差別，提出二元周期序列的對稱復(fù)雜度的概念；在第節(jié)中，計算二元周期序列的復(fù)雜度和對稱復(fù)雜度的期望值；在第節(jié)中，給出二元周期序列的復(fù)雜度和對稱復(fù)雜度的非平凡的下界；最后，在第節(jié)中，指出上最近兩篇論文的結(jié)果本質(zhì)上是一樣的。本章內(nèi)容來自作者論文，。§是一個奇數(shù)，它可以表示為，一，吼，。這些系數(shù)，夠可以看做圖，中反饋寄存器的抽頭（本圖來自文獻【）。下面給出的正式定義。定義跗一個由個系數(shù)，婦，這里岱，），和一個初姑記憶整數(shù)，一決定。如果在當(dāng)前時刻寄存器的內(nèi)容是（。一，。一，

34、。一，。一，），記憶整數(shù)的值是竹一，那么移位寄存器的操作規(guī)定為：求出整數(shù)和；。一一；將寄存器的內(nèi)容右移一位，輸出最右比特一，；將。別輸入最左邊的寄存器；第三章序列的統(tǒng)計性質(zhì)及二元周期序列的復(fù)雜度將記憶整數(shù)的值更新為。（盯一。）。整數(shù)一稱為的聯(lián)結(jié)整數(shù)（）。圖：帶進位的反饋移位寄存器（）定義對于二元終歸周期序列（，），它的定義為所有輸出序列為（，）的中最小的。如果。（，）是周期為丁的嚴(yán)格周期序列，令莖。吼。，那么一哿（一）。在集合；，）和集合舊（，。，）是二元終歸周期序列）之間存在一一對應(yīng)關(guān)系。我們也將集合，）中的元素稱為序列的有理表示。如果讀者想更多地了解有關(guān)數(shù)的知識，請看文獻】。如果（，），是

35、奇數(shù)，那么與一對應(yīng)的二元序列的最小周期為。（），這里。（）表示?？诘碾A。注上面的整數(shù)可以替換成任意素數(shù)，相應(yīng)的聯(lián)結(jié)整數(shù)）改變?yōu)槭鏀U，這里啦，。一果讀者想知道為什么一骱礦，請看文獻跗的第節(jié)。同樣地，改變?yōu)椋ǎ?，改變?yōu)檠弧薄ＦA（護一），一。下面我們給出復(fù)雜度的定義。定義（，）一條二元終歸周期序列，假設(shè)它的有理表示為一，（，），那么的復(fù)雜度蕾（）定義為實數(shù)（，）。注如果是全序列，規(guī)定圣（）。注如果。是周期為的周期序列，那么垂（）。第三章序列的統(tǒng)計性質(zhì)及二元周期序列的復(fù)雜度注一般情況下似時的復(fù)雜度定義是類似的，但在本文中我們只討論復(fù)雜度。下面給出一序列的定義，一序列是一序列的算術(shù)版本。定義對于一個紕，如果是它的聯(lián)結(jié)整數(shù)的本原根，我們稱這個嬙的輸出序列為一序列。由定義，一序列的周期為（），這里是歐拉函數(shù)。定義是一個正整數(shù)，如果是模的本原根，我們稱為的。如果口存在本原根，一定形為，。，或印，這里是一個奇素數(shù)，三。在第節(jié)和第節(jié)中我們僅考慮口。的情況，的情況是類似的。下面討論序列的綜合問題。與情況下的算法類似，和給出