幾類偽隨機(jī)序列的研究_圖文

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

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

3、非平凡下界。）指出上年和年的兩篇論文的結(jié)果本質(zhì)上是一祥的。）將周期序列的廣義離散傅立葉變換應(yīng)用到周期序列的線性復(fù)雜度的研究中去，構(gòu)造了許多具有大的線性復(fù)雜度的序列，改進(jìn)了的結(jié)果。）利用環(huán)上的指數(shù)和估計(jì)分析了兩類磊導(dǎo)出序列的獨(dú)立一樣式分布，證明了它們都是漸進(jìn)均勻的，所得結(jié)果改進(jìn)了以前的公開(kāi)結(jié)果。）利用環(huán)上的混合指數(shù)和估計(jì)與離散傅立葉變換，給出了環(huán)上的部分指數(shù)和估計(jì)。）利用環(huán)上的部分指數(shù)和估計(jì)，分析了兩類邑導(dǎo)出序列的部分周期分布和部分周期獨(dú)立一樣式分布，證明了它們也都是漸進(jìn)均勻的。摘要）利用函數(shù)域的擴(kuò)張構(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ù)域的擴(kuò)張。（），：（），一，揚(yáng)，：），），），邑），¨），：，研究成果聲明本人鄭重聲明：所提交的學(xué)位論文是我本人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作獲得的研究成果。盡我所知，文中除特別標(biāo)注和致謝的地方外，學(xué)位論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果，也不包含為獲得中國(guó)科學(xué)院電子學(xué)研究所或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)所使用過(guò)的材料。與我一同工作的合作者對(duì)此研究工作所做的任何貢獻(xiàn)均已在學(xué)位論文中作了明確的說(shuō)明并表示了謝意。特此申明。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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