有限域上本原多項(xiàng)式與不可約多項(xiàng)式判定(共53頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上摘要本文前面部分介紹了有限域理論的基礎(chǔ)知識(shí)。然后根據(jù)有限域的相關(guān)知識(shí)，對(duì)王鑫和王新梅在1中提出的判定不可約多項(xiàng)式及本原多項(xiàng)式的一種高效算法進(jìn)行了論證。該算法提出了三個(gè)條件作為判定有限域上多項(xiàng)式的不可約性的充要條件，并在有限域上多項(xiàng)式不可約的前提下，附加了一個(gè)條件作為判定有限域上多項(xiàng)式為本原多項(xiàng)式的充要條件。文章的后面部分，使用Microsoft Visual Studio 2008軟件，用c+語言編程實(shí)現(xiàn)了有限域上的模運(yùn)算、乘法運(yùn)算、快速指數(shù)算法、歐幾里得算法、整數(shù)分解算法等核心模塊，并最終實(shí)現(xiàn)了王鑫和王新梅在1中提出的判定方法，實(shí)現(xiàn)了對(duì)有限域上的多項(xiàng)式是否為不可約多

2、項(xiàng)式及本原多項(xiàng)式的判定。關(guān)鍵詞：有限域 不可約多項(xiàng)式 本原多項(xiàng)式專心-專注-專業(yè)ABSTRACTWe introduce the basic knowledge of finite fields theory in the front of this paper. According to the knowledge of finite fields, we discuss an efficient algorithm, which is used to determine whether a polynomial over finite fields is irreducible (prim

3、itive) or not, proposed by Wang Xin and Wang XinMei in 1. Three conditions are proposed by it as a necessary and sufficient condition to determine irreducible polynomials over the finite field. And under the precondition that the polynomial is irreducible over finite fields, the algorithm proposes a

4、 condition as the necessary and sufficient condition to determine whether a polynomial is primitive or not over finite fields. In the latter part, by using Microsoft Visual Studio 2008 software, we make the mode operations, multiplication operations, fast exponential algorithm, Euclid algorithm, int

5、eger factorization algorithm modules come true in c+ language. And finally achieved the decision method proposed by Wang Xin and Wang XinMei in 1, realized the determination that whether the polynomial over finite fields is irreducible (primitive) or not.Keywords：finite field irreducible polynomials

6、 primitive polynomials目錄第一章 緒論1.1 研究背景和研究意義有限域理論作為現(xiàn)代代數(shù)的重要分支，在密碼學(xué)，編碼理論，組合理論，大規(guī)模集成電路設(shè)計(jì)等諸多領(lǐng)域都發(fā)揮著重要作用，它的應(yīng)用極大地推動(dòng)了這些學(xué)科的發(fā)展，其中，許多相關(guān)領(lǐng)域的研究熱點(diǎn)都可以歸結(jié)為有限域理論中的關(guān)鍵問題，這使得有限域理論日益得到重視、充實(shí)和推動(dòng)。作為有限域理論研究的重要分支，有限域上的不可約多項(xiàng)式與本原多項(xiàng)式在密碼、編碼理論及隨機(jī)數(shù)的產(chǎn)生等方面有著尤其廣泛的應(yīng)用。例如偽隨機(jī)序列在擴(kuò)頻通信與序列密碼中被廣泛應(yīng)用，它可以在連續(xù)波雷達(dá)中被用作測(cè)距信號(hào)、在遙控系統(tǒng)中被用作遙控信號(hào)、在多址通信中被用作地址信號(hào)，在

7、數(shù)字通信中被用作群同步信號(hào)，還可被用作噪聲源在保密通信中起加密作用。這些偽隨機(jī)序列大部分是利用有限域上的不可約多項(xiàng)式和本原多項(xiàng)式，通過反饋移位寄存器和其它非線性邏輯產(chǎn)生的。另一方面，多項(xiàng)式理論尤其是不可約多項(xiàng)式和本原多項(xiàng)式又是分析偽隨機(jī)性能和密碼體制的一種有效工具，因此對(duì)限域上不可約多項(xiàng)式與本原多項(xiàng)式相關(guān)理論的研究具有重要的意義。作為使用有限域上不可約多項(xiàng)式和本原多項(xiàng)式的先決條件，如何快速得到有限域上的不可約多項(xiàng)式和本原多項(xiàng)式這一課題也一直沒有淡出人們的視線。如果沒有多項(xiàng)式的確定，又談何使用它？因此快速找出給定的有限域上給定次數(shù)的所有不可約多項(xiàng)式及本原多項(xiàng)式與快速確定給定的有限域上給定次數(shù)的多

8、項(xiàng)式是否為不可約多項(xiàng)式及本原多項(xiàng)式這兩個(gè)課題的重要性可想而知。本次畢業(yè)設(shè)計(jì)的題目是“有限域上不可約多項(xiàng)式與本原多項(xiàng)式的判定”，目前，對(duì)于這一課題的研究依舊在進(jìn)行，一些研究學(xué)者相繼提出自己的判定算法（文獻(xiàn)1、3等），但是尚無一個(gè)公認(rèn)的高效算法去實(shí)現(xiàn)有限域上多項(xiàng)式不可約性與本原多項(xiàng)式的快速判定。許多書中（文獻(xiàn)2、4等）等同樣提出了一些經(jīng)典的算法，但是由于其效率較低，無法滿足實(shí)際應(yīng)用的需求。但同時(shí)有限域上不可約多項(xiàng)式與本原多項(xiàng)式的應(yīng)用卻日益廣泛與重要，對(duì)于課題的研究已經(jīng)迫在眉睫。1.2 相關(guān)領(lǐng)域的研究進(jìn)展2004年，王澤輝和方小洵在文獻(xiàn)3中寫道，確定一個(gè)上次不可約多項(xiàng)式時(shí)，一般整系數(shù)多項(xiàng)式不可約性的

9、判定定理用不上，此時(shí)確定型（構(gòu)造性）算法技術(shù)上比較復(fù)雜，一般常采用概率型算法，目前較好的算法成功率為（較大時(shí)），需計(jì)算次多項(xiàng)式與次多項(xiàng)式的最小公因式，算法的時(shí)間復(fù)雜度為，屬于指數(shù)時(shí)間算法，而對(duì)于由低階構(gòu)造高階的解決方案要用到整數(shù)的標(biāo)準(zhǔn)分解。另外，確定一個(gè)次本原多項(xiàng)式的難度更大。他們?cè)谖墨I(xiàn)3中提出的方法是對(duì)于一大類整數(shù)（為素?cái)?shù)乘于素?cái)?shù)或的積），分別給出有限域上次多項(xiàng)式是不可約多項(xiàng)式與本原多項(xiàng)式的一個(gè)充要條件，該條件可以通過次上乘法加以驗(yàn)證，易于硬件實(shí)現(xiàn)。同時(shí)提出了可約多項(xiàng)式的一個(gè)充分條件，借此減少驗(yàn)證時(shí)間，并得到用次上乘法確定一個(gè)次不可約多項(xiàng)式及一個(gè)次本原多項(xiàng)式的高效算法。2009年，王鑫和王新

10、梅等人在其文獻(xiàn)1中提出了一個(gè)判定有限域上任一多項(xiàng)式是否為不可約多項(xiàng)式、本原多項(xiàng)式的高效確定算法，分析了多項(xiàng)式次數(shù)與其不可約因式之間的內(nèi)在聯(lián)系，給出了有限域上任意次多項(xiàng)式是否為不可約多項(xiàng)式，本原多項(xiàng)式的一個(gè)充要條件，通過利用歐幾里得算法，該判定僅需做次域上乘法，屬于多項(xiàng)式時(shí)間，易于硬件實(shí)現(xiàn)。他們提出的算法對(duì)文獻(xiàn)3中提出的算法有了很大的進(jìn)步，在判定過程中適用性更加廣泛。其他的一些判定算法大多出現(xiàn)在需要使用有限域上不可約多項(xiàng)式與本原多項(xiàng)式作為工具的課題中，并未單獨(dú)作為改進(jìn)算法或高效算法判定有限域上多項(xiàng)式不可約性和本原性提出，在此不做贅述。對(duì)于這一課題的研究從未間斷，但是所取得的成果每次都是曇花一現(xiàn)般

11、，兩個(gè)成果間的周期很長(zhǎng)，對(duì)于現(xiàn)階段對(duì)安全性要求越來越高的實(shí)際情況下，新的有限域上性能優(yōu)良的不可約多項(xiàng)式及本原多項(xiàng)式的發(fā)現(xiàn)十分重要，而現(xiàn)階段的算法也必將日漸無法滿足實(shí)際需要。1.3 本文主要的研究成果和內(nèi)容安排本文運(yùn)用文獻(xiàn)24中關(guān)于有限域的相關(guān)知識(shí)，對(duì)王鑫和王新梅等人在其文獻(xiàn)1中提出的判定有限域上不可約多項(xiàng)式與本原多項(xiàng)式的充要條件進(jìn)行了論證，而后使用Microsoft Visual Studio 2008軟件，用c+語言編程實(shí)現(xiàn)了有限域上的模運(yùn)算、乘法運(yùn)算、快速指數(shù)算法、歐幾里得算法、整數(shù)分解算法等核心模塊，并最終實(shí)現(xiàn)了王鑫和王新梅在1中提出的判定方法，實(shí)現(xiàn)了對(duì)有限域上的多項(xiàng)式是否為不可約多項(xiàng)式

12、及本原多項(xiàng)式的判定。論文的第一章為緒論部分，在緒論部分中，我們主要介紹了該課題研究背景、研究意義、研究現(xiàn)狀以及本文的研究成果和各章節(jié)結(jié)構(gòu)安排；在第二章中，參考文獻(xiàn)2，對(duì)域、有限域以及有限域上的多項(xiàng)式等知識(shí)點(diǎn)進(jìn)行了簡(jiǎn)要介紹，對(duì)基本定義以及相關(guān)的定理進(jìn)行了初步的描述與證明；第三章中對(duì)王鑫和王新梅等人在其文獻(xiàn)1中提出的判定有限域上不可約多項(xiàng)式與本原多項(xiàng)式的充要條件進(jìn)行了論證，其中引理的證明參考了文獻(xiàn)4中的相關(guān)知識(shí)。本次畢業(yè)設(shè)計(jì)我們使用Microsoft Visual Studio 2008軟件，用c+語言編程實(shí)現(xiàn)算法，在第四章中我們對(duì)實(shí)現(xiàn)判定有限域上不可約多項(xiàng)式及本原多項(xiàng)式的算法進(jìn)行了介紹，并對(duì)其中

13、的模運(yùn)算、乘法運(yùn)算、快速指數(shù)算法、歐幾里得算法、整數(shù)分解算法等核心模塊進(jìn)行了描述。第五章中我們對(duì)程序的運(yùn)行進(jìn)行了測(cè)試，使用的是文獻(xiàn)7中的上的30次以下的本原多項(xiàng)式。第六章為結(jié)論部分，對(duì)本次論文情況進(jìn)行了總結(jié)，并提出了本次課題的不足之處以及可以改進(jìn)的地方。第二章 有限域的基礎(chǔ)知識(shí)本章中，我們將對(duì)有限域理論的基本知識(shí)進(jìn)行介紹，作為下一章節(jié)中有限域上不可約多項(xiàng)式及本原多項(xiàng)式判定的鋪墊，章節(jié)中相關(guān)的定義及引理若無特殊標(biāo)注，則引自謝敏著的文獻(xiàn)2。2.1 群、環(huán)、域 本節(jié)中對(duì)群、環(huán)和域三種結(jié)構(gòu)進(jìn)行定義，為后面引出多項(xiàng)式環(huán)以及有限域的相關(guān)內(nèi)容做鋪墊。定義2.1.1（群） 設(shè)為某種元素組成的一個(gè)非空集合，若在

14、內(nèi)定義一個(gè)稱為乘法的運(yùn)算“”，滿足以下條件：（1）（封閉性），有；（2）（結(jié)合性），有；（3）在中有一個(gè)元素，對(duì)中任意元素，有，元素稱為單位元；（4）對(duì)中任一元素，都存在中的一個(gè)元素，使得，稱為可逆元，稱謂的逆元，記作，則稱關(guān)于“”形成一個(gè)群（Group），記作，通常在不混淆的情況下省略“”，用來表示一個(gè)群，也簡(jiǎn)記為。關(guān)于群的定義，我們特別需要注意以下兩點(diǎn)（一）群中的運(yùn)算并不一定可交換，但當(dāng)它滿足交換律時(shí)，則稱群為交換群或Abel群。（二）若非空集合中定義的運(yùn)算只滿足定義2.1.1中的條件（1）和（2），則稱為半群。定義2.1.2（環(huán)） 設(shè)為某種元素組成的一個(gè)非空集合，若在內(nèi)定義兩種運(yùn)算（通常

15、表示為加法運(yùn)算“”和乘法運(yùn)算“”）， 中所有元素滿足以下條件：（1）R關(guān)于加法運(yùn)算“”構(gòu)成一個(gè)Abel群；（2）R關(guān)于乘法運(yùn)算“”構(gòu)成一個(gè)半群；（3），有，即分配律成立。則稱R關(guān)于“”和“”形成一個(gè)環(huán)（Ring），記作，通常在不回產(chǎn)生混淆的情況下省略“”和“”，用來表示一個(gè)環(huán)。關(guān)于環(huán)的概念我們需要注意以下一點(diǎn)：（一）加法單位元一般記作，稱為零元。定義2.1.3 如果一個(gè)環(huán)中的非零元全體在乘法運(yùn)算“”下構(gòu)成群，則稱該環(huán)為除環(huán)（或斜域）。定義2.1.4（域） 可交換的除環(huán)稱為域。定義2.1.5 一個(gè)域如果包含有限個(gè)元素，則稱其為有限域，其元素的個(gè)數(shù)稱為該域的階。2.2 多項(xiàng)式環(huán) 本節(jié)對(duì)有限環(huán)上的多

16、項(xiàng)式的相關(guān)理論做簡(jiǎn)單介紹，因?yàn)橛邢蕲h(huán)上的多項(xiàng)式的許多定義以及性質(zhì)可以類推到有限域上，可以說，有限域上的多項(xiàng)式即是具有特殊限制條件的有限環(huán)上的多項(xiàng)式。設(shè)是一個(gè)環(huán)，是不屬于環(huán)的一個(gè)符號(hào)，是任意非負(fù)整數(shù)，形如，的形式和，叫做系數(shù)屬于環(huán)的的多項(xiàng)式，其中稱為環(huán)上的不定元，叫做該多項(xiàng)式的次項(xiàng)，叫做次項(xiàng)的系數(shù)。我們考慮環(huán)上的的多項(xiàng)式的全體，記為，對(duì)中的多項(xiàng)式而言，系數(shù)為零的項(xiàng)可以任意刪去和添上。因此，總可以假設(shè)中任意兩個(gè)多項(xiàng)式，含有相同次數(shù)的x的整數(shù)次冪，即可設(shè)，從而和相等，當(dāng)且僅當(dāng)對(duì)應(yīng)系數(shù)相等，即，定義中的加法運(yùn)算“”和乘法運(yùn)算“”如下：為定義乘法，記，定義其中。易知關(guān)于上述定義的加法運(yùn)算“”和乘法運(yùn)算“

17、”構(gòu)成環(huán)。中所有系數(shù)均為零的元素稱為零多項(xiàng)式，記為0（0表示零多項(xiàng)式或環(huán)中的零元，需視情況而定），它是中的加法零元，的加法逆元為定義2.2.1 關(guān)于上述加法運(yùn)算“”和乘法運(yùn)算“”構(gòu)成的環(huán)稱為環(huán)上的多項(xiàng)式環(huán)。定義2.2.2 設(shè)，則稱多項(xiàng)式的次數(shù)為，記為。稱為的首系數(shù)。若環(huán)含有單位元1，則將首系數(shù)為1的多項(xiàng)式稱為首一多項(xiàng)式。約定。定義2.2.3 設(shè)，。若存在，使得，則稱整除，記作。叫的因式，叫做的倍式。否則稱不能整除，記作。定義2.2.4 設(shè)，非常數(shù)。若有,使得，則或?yàn)槌?shù)（0次多項(xiàng)式），那么稱為多項(xiàng)式環(huán)中的不可約多項(xiàng)式或中的素元。定理2.2.1 設(shè)，則存在多項(xiàng)式，使得其中。定理2.2.2（唯一分

18、解定理） 設(shè)，則必有其中,，, 為中互不相同的不可約多項(xiàng)式，均為正整數(shù)，并且若不記不可約因式的次序，這個(gè)分解式是唯一的。定理2.2.3 設(shè)，則為域當(dāng)且僅當(dāng)為域上的不可約多項(xiàng)式。同類似，中的元素即為次數(shù)小于的次數(shù)的所有上的多項(xiàng)式，其中的加法、乘法運(yùn)算分別為模多項(xiàng)式的加法和乘法運(yùn)算。若，則。定義2.2.4 設(shè)，,若,則稱是的一個(gè)根。定理2.2.4 設(shè)，則是的一個(gè)根當(dāng)且僅當(dāng)。證 利用定理2.2.1，我們有其中,，將代入上式得從而由是的一個(gè)根的定義知定理成立。由定理2.2.4知，若在域上有根，則在上一定可約，反過來則不一定成立。定理2.2.5 設(shè)，則在上最多有個(gè)不同的根。定義2.2.5 設(shè)，正整數(shù)，若

19、 ，而則稱為的重根。定義2.2.6 設(shè)，稱為的一階導(dǎo)數(shù)。定理2.2.6 設(shè)，則為的重根當(dāng)且僅當(dāng)既是的根又是的根。證 設(shè)為的重根，由定義2.2.5知，而，設(shè)其中，則 由知，且而從而既是的根又是的根。是的根，設(shè)，則又因?yàn)槭堑母?，故從而必有繼而即為的重根。推論2.2.6 設(shè)，若為的重根，則為的重根。定義2.2.7 設(shè)，為域上個(gè)不全為零的多項(xiàng)式，首一多項(xiàng)式稱為，的最大公因式，是指滿足：（1），；（2）若有，則。可記為，。推論2.2.6 設(shè)，若，則沒有重根。定義2.2.8 當(dāng)，稱和互素。2.3 域的有限擴(kuò)張本節(jié)中，對(duì)有限域的結(jié)構(gòu)做簡(jiǎn)要介紹。定義2.3.1 設(shè)為一個(gè)域，為的一個(gè)非空子集，如果相對(duì)于中的加法

20、和乘法，也構(gòu)成一個(gè)域，則稱為的一個(gè)子域，為的一個(gè)擴(kuò)域（也稱為的一個(gè)擴(kuò)張）。定義2.3.2 沒有真子域的域稱為素域。定義2.3.3 設(shè)是的一個(gè)子域，。若存在，使得，則稱為上的代數(shù)元，否則稱為超越元。若擴(kuò)域中的元素都為上的代數(shù)元，則稱為的代數(shù)擴(kuò)域（或代數(shù)擴(kuò)張）。假設(shè)是上的代數(shù)元，考慮集合對(duì)任意，有即，。又因?yàn)?，有即，。所以是的一個(gè)理想，稱為代數(shù)元在中的零化理想。又由為主理想整環(huán)知，存在，使得若限定為首一多項(xiàng)式，則由唯一確定。定義2.3.4 以上由代數(shù)元唯一確定的首一多項(xiàng)式，稱為在上的極小多項(xiàng)式。在上的次數(shù)指的次數(shù)。定理2.3.1 設(shè)為上的代數(shù)元，則其在上的極小多項(xiàng)式滿足：（1）為中的不可約多項(xiàng)式；

21、（2）任意屬于，。證 （1）為的一個(gè)根，故若，且，則從而或而，是不可能的。因此，為中的不可約多項(xiàng)式。(2)由的定義即知由上分析知，是中以為根的多項(xiàng)式中次數(shù)最小者。定義2.3.5 為域的一個(gè)擴(kuò)張，將看成上的向量空間，若是有限維的，則稱為的有限擴(kuò)張，上向量空間的維數(shù)稱為擴(kuò)張次數(shù)，記為。定理2.3.2 域K的每一個(gè)有限擴(kuò)張都是代數(shù)擴(kuò)張。證 設(shè)為的有限擴(kuò)張，則對(duì)中任一元素來說，這個(gè)元素作為的向量關(guān)于是線性相關(guān)的，故存在一組不全為零的元素，使得這就說明是上的代數(shù)元，從而是的代數(shù)擴(kuò)張。定理2.3.3 設(shè)為上的次代數(shù)元，為在上的極小多項(xiàng)式，則（1）；（2），且，為在上的一組基。2.4 有限域的性質(zhì)本節(jié)中，我

22、們通過幾個(gè)定理來探討有限域的性質(zhì)。定理2.4.1 設(shè)為一個(gè)有限域，則，其中為的特征，為在其素域上的擴(kuò)張次數(shù)。定理2.4.2 為階有限域，則對(duì)任意，有。定理2.4.3 設(shè)，為素?cái)?shù)，則必存在一個(gè)階有限域，并且在同構(gòu)的意義下，這個(gè)域是唯一的。定理2.4.4 設(shè)為一個(gè)階有限域，則的每一子域的階形如，其中為的正因子。反之，若為的正因子，則恰有一個(gè)階子域，且中的元素屬于當(dāng)且僅當(dāng)。定理2.4.5 有限域的乘法群是一個(gè)循環(huán)群。定義2.4.1 循環(huán)群的生成元稱為有限域的本原元。定理2.4.6 設(shè)為一有限域，為其有限擴(kuò)張，則為的單擴(kuò)域，即，其中為的任一本原元。2.5 有限域上的多項(xiàng)式在本節(jié)中，我們將多有限域上的多

23、項(xiàng)式的相關(guān)定義及定理做簡(jiǎn)單的介紹。由前面章節(jié)介紹的內(nèi)容知道，若為一次不可約首一多項(xiàng)式，是的一個(gè)根，則，稱為的極小多項(xiàng)式。但是不一定是的本原元。我們將根為本原元的極小多項(xiàng)式稱為本原多項(xiàng)式。定義2.5.1 設(shè)為有限域上的一個(gè)次不可約首一多項(xiàng)式，若的根為的本原元，則稱為中的本原多項(xiàng)式。定義2.5.2 設(shè)，稱使得成立的最小正整數(shù)為多項(xiàng)式的周期或階，記為。定理2.5.1 設(shè)為有限域上的一個(gè)次不可約多項(xiàng)式，為的一個(gè)根，則的全部根為，并且這個(gè)根是互異的。定理2.5.2 設(shè)為一次不可約多項(xiàng)式，則等于在中任一根的階，特別地，為本原多項(xiàng)式當(dāng)且僅當(dāng)。定理2.5.3 設(shè)是的擴(kuò)域中的元素，則在中的極小多項(xiàng)式為其中為的次

24、數(shù)，它由 決定，并且。2.6 本章小結(jié)在本章中，我們主要對(duì)域、有限域以及有限域上的多項(xiàng)式等知識(shí)點(diǎn)進(jìn)行了簡(jiǎn)要介紹，對(duì)基本定義以及相關(guān)的定理進(jìn)行了初步的描述與證明，意在為下一章中介紹有限域上不可約多項(xiàng)式與本原多項(xiàng)式的判定方法做出鋪墊，章內(nèi)相關(guān)定義及定理參考謝敏著文獻(xiàn)2中相關(guān)內(nèi)容。第三章 有限域上不可約多項(xiàng)式和本原多項(xiàng)式的判定方法3.1 引言在本章中，根據(jù)文獻(xiàn)2、4中的已有的公理及定理，證明了王鑫，王新梅等人在文獻(xiàn)1中提出的判定有限域上的次多項(xiàng)式為不可約多項(xiàng)式的充要條件，以及判定有限域上的次多項(xiàng)式為本原多項(xiàng)式的充要條件，本章所證明的判定方法將作為后面有限域上不可約多項(xiàng)式與本原多項(xiàng)式判定程序?qū)崿F(xiàn)的依據(jù)

25、。3.2 有限域上多項(xiàng)式不可約性的判定本節(jié)中根據(jù)文獻(xiàn)2、4中關(guān)于有限域以及有限域上的多項(xiàng)式的相關(guān)知識(shí)，論證了判定有限域上的次多項(xiàng)式為不可約多項(xiàng)式的充要條件。定義3.2.11 設(shè),非常數(shù)。若有,使得，則或?yàn)槌?shù)（0次多項(xiàng)式），那么稱為多項(xiàng)式環(huán)中的不可約多項(xiàng)式或中的素元。設(shè)是上的一個(gè)次多項(xiàng)式，上的多項(xiàng)式，滿足整除，則稱，對(duì)模同余，記為.我們知道，如果存在一個(gè)上的次不可約多項(xiàng)式，取為模，對(duì)上的全體多項(xiàng)式進(jìn)行等價(jià)分類，那么它的剩余系， 含有個(gè)不同的多項(xiàng)式.2(1)叫做模的一組完全剩余系，除去0叫做模的一組縮系對(duì)于一般的上的次多項(xiàng)式，(1)也是模的一組完全剩余系，其中與互素的全體多項(xiàng)式叫做模的一組縮系2

26、我們定義(1)中的加法和乘法與多項(xiàng)式的相同，但所得和、積要用去除在這樣的定義下，運(yùn)算是封閉的在這兩個(gè)運(yùn)算下，的剩余系(1)構(gòu)成一個(gè)含個(gè)元素的有限域，它是的一個(gè)擴(kuò)域，記為我們還知道任一有限域的元素個(gè)數(shù)一定是某個(gè)素?cái)?shù)p的方冪，而且在同構(gòu)意義下，元素個(gè)數(shù)相等的有限域是唯一的2引理3.2.12 如果有一個(gè)上的次不可約多項(xiàng)式，那么它一定是的因式。證 設(shè)次不可約多項(xiàng)式的縮系是，.設(shè)不整除，與整數(shù)縮系的性質(zhì)類似，此時(shí)， 也是一縮系，所以有 ，或?qū)ι先我庖粋€(gè)多項(xiàng)式，都有取，就得到.證完2引理3.2.22 設(shè)是一個(gè)次不可約多項(xiàng)式，且，則.證 設(shè)，由 ，所以.對(duì)于模，有個(gè)不同的多項(xiàng)式由于同余方程根的個(gè)數(shù)不超過，故

27、， 證完2引理3.2.32 設(shè)，則.證 不妨設(shè)，由輾轉(zhuǎn)相除法得， ，, ,其中.因此，.由此即得. 證完引理3.2.42 在定理4.1.2的條件下，則有整除.證 可設(shè)，由整除，可得整除，再由定理4.1.3得整除，故.另一方面由定理4.1.2，于是，即得整除.引理3.2.52 在上，多項(xiàng)式無重因式.證 在特征為的域上，多項(xiàng)式如果有重因式，仍有的次數(shù)大于零.設(shè)，則，于是，故無重因式，由不整除，便知無重因式. 證完2引理3.2.61 為一有限域，其中，則：，其中是上所有次首一不可約多項(xiàng)式的乘積。證 由引理3.2.4知，是一個(gè)次不可約多項(xiàng)式，再加上引理3.2.5已經(jīng)證明無重因式，不難推斷出引理3.2.

28、6中的結(jié)論。該引理表明: 實(shí)際上是由上次數(shù)整除的所有（相異，沒有重復(fù)的）首一不可約多項(xiàng)式的乘積所構(gòu)成。例如：當(dāng),就等于上的所有的1、2、3和6次首一不可約多項(xiàng)式乘積。引理3.2.71 次多項(xiàng)式,設(shè)的所有不可約因式為，)，則當(dāng)且僅當(dāng), ，且對(duì)所有，)均有。證 由引理3.2.5知沒有重因式，再由引理3.2.6，該結(jié)論成立。設(shè)自然數(shù)的因式分解為, 為素?cái)?shù)，是正整數(shù)，)，用表示對(duì)應(yīng)的，令 ,，,則有：引理3.2.81 上的次多項(xiàng)式為不可約多項(xiàng)式的充要條件是：（1）；（2）對(duì)任意，;（3）對(duì)任意的,均有，首先對(duì)上述三個(gè)條件做簡(jiǎn)單的解釋。條件（1）旨在說明是由以的因子為次數(shù)的不可約多項(xiàng)式之積；（2）表明無

29、一次因式；（3）是為了說明事實(shí)上并不含有次數(shù)小于的不可約因式。因此只能為一次不可約因式。證 為了證明定理3.2.8，首先要證明這樣一個(gè)結(jié)論：對(duì)任意的自然數(shù),有成立。事實(shí)上，設(shè)，那么。因?yàn)槭撬財(cái)?shù)，故,從而。反之，設(shè)，則對(duì)，有，且至少存在一個(gè)滿足 (否則與矛盾)。故，。由引理3.2.6，為不可約多項(xiàng)式，故（1）成立。而由題設(shè)，的次數(shù)是大于等于2的，因此條件（2）成立。又對(duì)任意的，成立。否則，設(shè)，。因?yàn)槭遣豢杉s多項(xiàng)式，且，故有，從而,再由引理3.2.4，這與矛盾。故（3）成立。 由于無重因式，所以無重因式，故可設(shè)在的因式分解為：，其中為的互不相同的不可約因式。由條件（2）知，因無一次因式，即均非一次

30、因式，故有，從而。又因?yàn)?，所以（?duì)任意的）(否則，若存在因式，則有，進(jìn)而，這與，矛盾)。因此，再由引理證明的一開始所證結(jié)論，可得，因此的次數(shù)只能為，而為不可約多項(xiàng)式，所以首一時(shí)，即為一不可約多項(xiàng)式。3.3 有限域上多項(xiàng)式本原性的判定定義3.3.11 設(shè)是上次不可約多項(xiàng)式。如果滿足的最小正整數(shù)為，則稱為上的本原多項(xiàng)式。定理3.3.11 上的次多項(xiàng)式為本原多項(xiàng)式的充要條件是：（1）為上的不可約多項(xiàng)式。（2）對(duì)的任意因子（大于1），均有.證 必要性顯然，下證充分性。為不可約多項(xiàng)式。（反證）設(shè)存在,使得。因，從而，,設(shè),及的素因子為，則也為的素因子，因此存在正整數(shù)，使得，也即。那么由上述,可得,也即，

31、與條件（2）矛盾。故對(duì)任意的t，均有，即為本原多項(xiàng)式。3.4 本章小結(jié)在本章中，論證了王鑫，王新梅等人在文獻(xiàn)1中提出的判定有限域上不可約多項(xiàng)式與本原多項(xiàng)式的充要條件，其中，上的次多項(xiàng)式為不可約多項(xiàng)式的充要條件是：（1）；（2）對(duì)任意，;（3）對(duì)任意的,均有，上的次多項(xiàng)式為本原多項(xiàng)式的充要條件是：（1）為上的不可約多項(xiàng)式。（2）對(duì)的任意因子（大于1），均有.根據(jù)這兩個(gè)充要條件，我們編程實(shí)現(xiàn)了有限域上不可約多項(xiàng)式與本原多項(xiàng)式的判定。第四章 程序?qū)崿F(xiàn)在本章中，我們主要介紹了實(shí)現(xiàn)有限域上不可約多項(xiàng)式和本原多項(xiàng)式判定算法的程序?qū)崿F(xiàn)部分，該部分的核心思想即是第三章中提出的判定有限域上多項(xiàng)式為不可約多項(xiàng)式和

32、本原多項(xiàng)式的充要條件。4.1 程序總流程本次畢業(yè)設(shè)計(jì)的判定部分程序?qū)崿F(xiàn)的主流程圖如下：圖4.1.1 程序判定部分主流程圖如圖4.1.1所示，程序根據(jù)使用者輸入的有限域的階以及有限域上的多項(xiàng)式，首先判定該多項(xiàng)式是否為有限域上的不可約多項(xiàng)式，而后在其在有限域上不可約的前提下，判定其在有限域上的本原性，最終輸出判定結(jié)果。4.2 數(shù)據(jù)結(jié)構(gòu)本節(jié)主要介紹實(shí)現(xiàn)有限域上不可約多項(xiàng)式和本原多項(xiàng)式判定的程序的數(shù)據(jù)結(jié)構(gòu)以及其上的基本操作。4.2.1 有限域上多項(xiàng)式的表示我們采用類的變量類型存儲(chǔ)有限域上的多項(xiàng)式，定義多項(xiàng)式類及其成員變量的代碼如下class Polynomialunsigned int ord;vec

33、tor<int> pol;其中，無符號(hào)整型變量ord用于存儲(chǔ)有限域的階；整型向量pol用于存儲(chǔ)多項(xiàng)式的系數(shù)，其中，向量的第n位存儲(chǔ)多項(xiàng)式相應(yīng)次數(shù)為n的變量系數(shù)，例如對(duì)于多項(xiàng)式x5+4x2+x+3,存儲(chǔ)為向量的形式即3,1,4,0,0,1。4.2.2 多項(xiàng)式讀入模塊多項(xiàng)式讀入模塊pol_s_in( )定義為class Polynomial public:void pol_s_in( unsigned int a , string b );/*用字符串構(gòu)造多項(xiàng)式類*/;該模塊主要實(shí)現(xiàn)了將字符串型的多項(xiàng)式轉(zhuǎn)化為4.1.1節(jié)中的向量類型，以供后續(xù)模塊使用。4.2.3 運(yùn)算符根據(jù)程序設(shè)計(jì)的需

34、要，重載了取模運(yùn)算“%”、乘法運(yùn)算“*”、判斷是否相等運(yùn)算符“=”。分別實(shí)現(xiàn)了基于多項(xiàng)式向量以及有限域的階的三種運(yùn)算該部分定義如下： class Polynomial public:friend Polynomial operator%( Polynomial& a , Polynomial& b );friend Polynomial operator*( Polynomial& a , Polynomial& b );friend bool operator=( Polynomial& a , Polynomial& b ); ;4.3 基礎(chǔ)

35、算法本節(jié)主要介紹實(shí)現(xiàn)判定有限域上多項(xiàng)式不可約性和本原性的過程中用到的主要數(shù)學(xué)算法及其程序?qū)崿F(xiàn)。4.3.1 快速指數(shù)算法在判定算法實(shí)現(xiàn)的過程中，需要計(jì)算形如的運(yùn)算，程序?qū)崿F(xiàn)過程中，對(duì)于整除性的判斷，我們使用來判別其是否整除，顯然當(dāng)和過大時(shí)，計(jì)算代價(jià)將會(huì)相當(dāng)大，因此，在這里們使用快速指數(shù)算法進(jìn)行計(jì)算。實(shí)現(xiàn)快速指數(shù)算法的程序流程圖如圖4.3.1.1所示（見下頁）：圖4.3.1 快速指數(shù)算法4.3.2 整數(shù)分解算法在4.4節(jié)不可約性判定中，第三步涉及將一個(gè)整數(shù)的全部素因子找到并用于后續(xù)判定，在此，我們涉及了算法實(shí)現(xiàn)了快速找到的全部素因子，算法的流程圖如圖4.3.2.1：圖4.3.2.14.3.3 歐幾

36、里得算法4.4 不可約性判定根據(jù)第三章的相關(guān)知識(shí)介紹，不可約性的判定分為三步，流程如下：圖4.4.1其中的三個(gè)判定模塊的實(shí)現(xiàn)如下：（1）根據(jù)充要條件中的第一條，的判定由快速指數(shù)算法實(shí)現(xiàn)，計(jì)算，代碼如下if( !(fastExponentialAlgorithm(p,pol.size()-1) = Q1 ) ) return false;其中Q1為多項(xiàng)式“1”。（2）根據(jù)充要條件中的第二條，對(duì)于，計(jì)算所有是否為0。for(int i = 0,n,sum ; i < ord ; i+ )n = i ;sum = pol0 ;for( unsigned int j = 1 ; j<pol

37、.size() ; j+ )sum = ( sum + polj * n ) % ord + ord ) % ord ;n = n * i % ord;if(sum = 0)return false;（3）首先使用整數(shù)分解算法將多項(xiàng)式的最高次項(xiàng)次數(shù)分解，存儲(chǔ)于向量vfac中vFac = factorization( pol.size()-1 );然后首先使用快速指數(shù)算法求出的余數(shù)，然后使用歐幾里得算法求出，如果結(jié)果為多項(xiàng)式“1”則通過（1）（2）（3）步最終判定為不可約多項(xiàng)式。4.5 本原性判定參照不可約性判定的條件（1），使用快速指數(shù)算法容易實(shí)現(xiàn)對(duì)的任意因子（大于1），均有的判定，結(jié)合4.4

38、節(jié)中不可約性的判定，最終確定多項(xiàng)式為有限域上的本原多項(xiàng)式。第五章 程序測(cè)試程序的測(cè)試數(shù)據(jù)為有限域上30次以下的本原多項(xiàng)式，數(shù)據(jù)來自參考文獻(xiàn)7的附錄A部分，圖5.1為輸入數(shù)據(jù)，圖5.2和圖5.3為程序運(yùn)行結(jié)果。圖5.1 測(cè)試用本原多項(xiàng)式圖5.2 程序開始界面圖5.3 測(cè)試結(jié)果圖5.3由于篇幅有限，故未將所有多項(xiàng)式結(jié)果體現(xiàn)出來，全部30個(gè)多項(xiàng)式通過測(cè)試。該程序還可以通過手動(dòng)輸入有限域的階以及多項(xiàng)式的方式進(jìn)行測(cè)試多項(xiàng)式在有限域上的不可約性和本原性，見圖5.4。圖5.4 手動(dòng)輸入多項(xiàng)式測(cè)試第六章 總結(jié)與展望本文運(yùn)用文獻(xiàn)24中關(guān)于有限域的相關(guān)知識(shí)，對(duì)王鑫和王新梅等人在其文獻(xiàn)1中提出的判定有限域上不可約多

39、項(xiàng)式與本原多項(xiàng)式的充要條件進(jìn)行了論證，而后使用Microsoft Visual Studio 2008軟件，用c+語言編程實(shí)現(xiàn)了有限域上的模運(yùn)算、乘法運(yùn)算、快速指數(shù)算法、歐幾里得算法、整數(shù)分解算法等核心模塊，并最終實(shí)現(xiàn)了王鑫和王新梅在1中提出的判定方法，實(shí)現(xiàn)了對(duì)有限域上的多項(xiàng)式是否為不可約多項(xiàng)式及本原多項(xiàng)式的判定。在實(shí)現(xiàn)本次課題的過程中，發(fā)現(xiàn)以下地方還存在不足，有后續(xù)的研究?jī)r(jià)值：（1）在算法的循環(huán)中，多項(xiàng)式的平方操作被大量重復(fù)，如何提高多項(xiàng)式平方操作的效率是值得思考的。在文獻(xiàn)3中，提出了在擴(kuò)域上的快速乘法算法，通過分析快速模約簡(jiǎn)算法、求逆算法、中國(guó)剩余定理（CRT）、多項(xiàng)式乘法等算法后，結(jié)合W

40、inograd短卷積算法，討論模多項(xiàng)式的因子項(xiàng)的選擇對(duì)于有限擴(kuò)域乘法的乘法次數(shù)和減法次數(shù)的影響，從而得出關(guān)于模多項(xiàng)式的最優(yōu)選擇問題，很大程度上提高了擴(kuò)域上乘法的效率，與本文中的算法相結(jié)合可以提高一定的效率。（2）本文的算法實(shí)現(xiàn)全部為軟件實(shí)現(xiàn)，而實(shí)際應(yīng)用中算法的一些模塊可以用硬件來實(shí)現(xiàn)，這樣可以在很大程度上提高有限域上不可約多項(xiàng)式與本原多項(xiàng)式的判定時(shí)間，如何將軟件與硬件相結(jié)合來完成判定是下一步研究的方向之一。（3）算法面向的有限域上的一般多項(xiàng)式，而目前有許多研究方向針對(duì)有限域上的一些有特點(diǎn)的多項(xiàng)式，比如文獻(xiàn)8中提出的對(duì)于一大類整數(shù)（為素?cái)?shù)乘于素?cái)?shù)或1的積），分別各處有限域上次多項(xiàng)式是不可約多項(xiàng)式

41、與本原多項(xiàng)式的一個(gè)充要條件，該條件可通過次上乘法加以驗(yàn)證，易于硬件實(shí)現(xiàn)，等等情況，之后的一個(gè)研究方向可以將有限域上的多項(xiàng)式進(jìn)行一定的分類，首先判定多項(xiàng)式的特殊性，而后“因式而異”進(jìn)行判斷，以提高效率。（4）有限擴(kuò)域上的多項(xiàng)式由于僅系數(shù)的形式域素域上不同，對(duì)判定定理無影響，因此沒有在程序中單獨(dú)實(shí)現(xiàn)，但是現(xiàn)實(shí)中擴(kuò)域上的多項(xiàng)式應(yīng)用也是非常廣泛，因此，在擴(kuò)域上的多項(xiàng)式的表現(xiàn)形式以及程序的算法實(shí)現(xiàn)上還是大有文章的，后續(xù)研究可以基于有限擴(kuò)域上的多項(xiàng)式如何表示以及運(yùn)算如何進(jìn)行來開展研究。致謝首先感謝我的畢業(yè)設(shè)計(jì)導(dǎo)師謝敏，在整個(gè)的畢業(yè)設(shè)計(jì)過程中，她不但及時(shí)對(duì)我的畢業(yè)設(shè)計(jì)作出指導(dǎo)，并且能夠及時(shí)為我答疑解惑，甚至

42、犧牲自己的休息時(shí)間來輔導(dǎo)我的畢業(yè)設(shè)計(jì)，同時(shí)，在教導(dǎo)畢業(yè)設(shè)計(jì)課題相關(guān)知識(shí)的同時(shí)，她更注重培養(yǎng)我獨(dú)立分析問題，查閱資料，提出假設(shè)，解決問題的能力，是我在完成畢業(yè)設(shè)計(jì)的同時(shí)，更學(xué)習(xí)到了如何進(jìn)行科學(xué)研究，如何合理利用自己的時(shí)間主動(dòng)學(xué)習(xí)，這些收獲令我獲益匪淺。其次要感謝我的女朋友魏雯，她在我畢業(yè)設(shè)計(jì)的過程中一直督促我，鼓勵(lì)我，讓我對(duì)于完成這次挑戰(zhàn)充滿了信心和決心，在她的幫助下，我克服了許多來自自己方面的障礙，知道最終完成我的畢業(yè)設(shè)計(jì)。最后，還要感謝我的朋友們，他們?cè)谖耶厴I(yè)設(shè)計(jì)的過程中，給予我莫大的幫助，提供給我舒適的學(xué)習(xí)氛圍，讓我能夠安心完成自己的畢業(yè)設(shè)計(jì)。參考文獻(xiàn)1 王鑫，王新梅，韋寶典.判定有限域上

43、不可約多項(xiàng)式及本原多項(xiàng)式的一種高效算法.中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2009 48（1）2 謝敏，信息安全數(shù)學(xué)基礎(chǔ)，西安電子科技大學(xué)出版社。2006.113 王澤輝，方小洵.Fp上不可約多項(xiàng)式與本原多項(xiàng)式的高效確定算法J.中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2004 43（6）：89-924 柯召，孫琦.數(shù)論講義M.北京:高等教育出版社，20035 MCELIECE R J Finite field for computer scientists and engineersM.Boston Kluwer Academic Publisher 1987.6 錢能，C+程序設(shè)計(jì)教程，清華大學(xué)出版社。2005.

44、97 靳蕃，組合設(shè)計(jì)與編碼，工業(yè)技術(shù)圖書館。1990.58 余光雷，擴(kuò)域的乘法及其快速實(shí)現(xiàn).中山大學(xué)學(xué)報(bào)2010.5附錄程序源代碼如下：Hello.h該文件打印出歡迎界面#ifndef HELLO#define HELLO#include<iostream>using namespace std;void hello()cout<<"/"<<endl;cout<<"/ 本科畢業(yè)設(shè)計(jì) /"<<endl;cout<<"/ 有限域上不可約多項(xiàng)式和本原多項(xiàng)式的判定 /"&

45、lt;<endl;cout<<"/ 學(xué)號(hào)： 姓名：周博 導(dǎo)師：謝敏 /"<<endl;cout<<"/"<<endl;#endifpolynomial.h該文件實(shí)現(xiàn)了有限域上多項(xiàng)式類的定義以及算法函數(shù)的聲明#ifndef POLYNOMIAL#define POLYNOMIAL#include<vector>#include<iostream>#include<string>using namespace std;class Polynomialunsigned i

46、nt ord;vector<int> pol;public:Polynomial()Polynomial( unsigned int a , vector<int>& b);/直接用向量構(gòu)造多項(xiàng)式類void pol_s_in( unsigned int a , string b );/*用字符串構(gòu)造多項(xiàng)式類*/bool is_zero()if(pol.size()=0)return true;return false;bool is_irr();/*判定多項(xiàng)式是否不可約*/bool is_pri();/*判斷是否為本原多項(xiàng)式*/friend Polynomial

47、 operator%( Polynomial& a , Polynomial& b );/*重載取余函數(shù)*/friend Polynomial operator*( Polynomial& a , Polynomial& b );/*重載乘法函數(shù)*/friend bool operator=( Polynomial& a , Polynomial& b ) if( a.ord = b.ord && a.pol = b.pol ) return true ; return false ; /*重載判斷相等符號(hào)*/friend Pol

48、ynomial fastExponentialAlgorithm(Polynomial& a,unsigned int b);/*快速指數(shù)算法求模*/;Polynomial EuclideanAlgorithm( Polynomial& a , Polynomial& b );/*歐幾里得算法*/vector<int> factorization( int n );/*整數(shù)分解*/#endifpolynomial.cpp該文件實(shí)現(xiàn)了多項(xiàng)式的構(gòu)造函數(shù)、多項(xiàng)式讀入函數(shù)、有限域上多項(xiàng)式不可約性及本原性的判定函數(shù)#include"polynomial.h&

49、quot;Polynomial:Polynomial(unsigned int a, vector<int> &b )ord = a;pol = b;for(unsigned int i = 0 ; i < pol.size() ; i+ ) poli = ( poli % ord + ord ) % ord ;/*多項(xiàng)式系數(shù)按階取模*/void Polynomial:pol_s_in( unsigned int a , string b )unsigned int sum=0;/*用于存儲(chǔ)多項(xiàng)式的系數(shù)*/unsigned int o=0;/*用于存儲(chǔ)多項(xiàng)式的次數(shù)*/

50、ord=a;for(unsigned int i=0;i<b.size()&&bi!='+'i+)sum=0;o=0;while(i<b.size()&&bi<='9'&&bi>='0')sum=sum*10+bi-'0'i+;if(sum=0) sum=1;if(bi='x')i+;if(bi='')i+;while(i<b.size()&&bi<='9'&&bi&g

51、t;='0')o=o*10+bi-'0'i+;else o=1;if(pol.size()<o+1)pol.assign(o+1,0);polo=sum;bool Polynomial:is_irr()Polynomial p(ord,pol);vector<int> vFac;/*存儲(chǔ)整數(shù)分解后的結(jié)果*/unsigned int pOrd = pol.size()-1;/*多項(xiàng)式最高次項(xiàng)次數(shù)*/if(pOrd=1) return true;Polynomial Q1;Q1.pol_s_in( ord ,"1");/*多項(xiàng)式

52、“”*/step 1判斷f（x）是否是以n的因子為次數(shù)的不可約多項(xiàng)式之積-if( !(fastExponentialAlgorithm(p,pol.size()-1) = Q1 ) ) return false; /step 1結(jié)束-/step 2判斷f（x）是否有一次因式-for(int i = 0,n,sum ; i < ord ; i+ )n = i ;sum = pol0 ;for( unsigned int j = 1 ; j<pol.size() ; j+ )sum = ( sum + polj * n ) % ord + ord ) % ord ;n = n * i

53、% ord;if(sum = 0)return false;/step 2結(jié)束-/step 3判斷f（x）中是否含有次數(shù)小于n的不可約因式-vFac = factorization( pol.size()-1 );for( unsigned int i = 0 ; i < vFac.size() ; i+ )if( !(EuclideanAlgorithm( p , fastExponentialAlgorithm( p , ( pol.size() - 1 ) / vFaci ) ) = Q1) ) return false; /step 3結(jié)束-return true;bool Polynomial:is_pri()Poly