不可約多項式的性質(zhì)和判定 論文

不可約多項式的性質(zhì)和判定摘要數(shù)論中許多有關整數(shù)的概念和結論可以推廣到多項式上去。本文首先將整數(shù)的算術基本定理推廣到多項式理論中，得到多項式的基本定理；然后將素數(shù)的一些性質(zhì)推廣得到不可約多項式的一些性質(zhì)；最后介紹素性檢驗常用方法，相應地，論述了不可約多項式的常用判別法。關鍵詞：素數(shù)，多項式，算術基本定理。AbstractManyconceptsandconclusionsaboutintegersinnumbertheorycanbeextendedtopolynomials.Wefirstdeducethefundamentaltheoremofarithmetictopolynomialtheory,andobtainthefundamentaltheoremofpolynomials.Thenweextendsomepropertiesofprimenumberstosomepropertiesofirreduciblepolynomials.Finally,thecommonmethodsofprimalitytestareintroduced.Accordingly,thecommondiscriminantmethodsofirreduciblepolynomialsarediscussed.Keywords:Primes,Polynomials,FundamentalTheoremsofArithmetic.目錄引言3第二章算術基本定理及其在多項式情形下的推廣6第三章素數(shù)的性質(zhì)及其在多項式情形下的推廣10第四章素性檢驗以及不可約多項式的判定13參考文獻19第一章引言整數(shù)和多項式是數(shù)論的主要研究對象之一。在數(shù)論研究中，一個常用的研究方法就是把有關整數(shù)成立的結論推廣到多項式中去，我們發(fā)現(xiàn)，大多數(shù)情形下，結論驚人的類似。例如將整數(shù)的帶余除法、輾轉(zhuǎn)相除法、中國剩余定理推廣到多項式中去（[2]、[7]等中都有具體的介紹），當然，也有不同的結論。如整數(shù)環(huán)是主理想整環(huán)（它的每個理想都是主理想），而多項式環(huán)一般不是主理想整環(huán)。例如整系數(shù)多項式環(huán)中(2,x)就不是一個主理想（詳細證明見[19]），所以不是主理想整環(huán)。本文將從算術基本定理（定理2.1.1）出發(fā)，介紹算術基本定理的內(nèi)容及其證明過程，并將其推廣到多項式中得到類似的結論。整數(shù)的研究重點是素數(shù)，素數(shù)十分有趣，有許多關于素數(shù)的問題表述它們都很簡單，但證明卻十分困難。有許多關于素數(shù)的猜想至今還沒能得到解決。古希臘數(shù)學家埃拉托斯特尼（Eratosthenes）發(fā)明了一種尋找素數(shù)的篩法，通過篩掉剩下的數(shù)的倍數(shù)得到給定范圍的素數(shù)（詳見4.1），通過篩法我們能夠得到許多素數(shù)，但素數(shù)是否有無窮多個？這個問題在2000多年前由歐幾里得（Euclid）證明：素數(shù)確實有無窮多個（詳見3.1）。容易證明除了2和3以外，任意兩個相鄰素數(shù)（我們稱兩個素數(shù)為相鄰的，如果它們之間不存在其它的素數(shù)）的差都是2的倍數(shù)，我們稱相差為2的兩個素數(shù)為孿生素數(shù)。隨意給出一小列素數(shù)：13、17、19、23、29、31，我們可以發(fā)現(xiàn)（17，19）、（29，31）每一對中的兩個素數(shù)的差都是2，因此它們都是孿生素數(shù)。那么是否有無窮多對這樣的數(shù)呢？這就是著名的孿生素數(shù)猜想，但這個猜想如何證明是一大難題，甚至是它的“弱形式”都不知道是否成立，但在2013年數(shù)學家張益唐運用篩法證明了“存在無窮多個之差小于7000萬的素數(shù)對”（[8]），使得對孿生素數(shù)猜想的研究取得了重大突破。與孿生素數(shù)猜想有著密切聯(lián)系的是哥德巴赫猜想：“任意大于2的偶數(shù)都可以寫成兩個素數(shù)之和?！?742年哥德巴赫（Goldbach）寫信請教歐拉（Euler）該如何證明這個猜想，遺憾的是歐拉（Euler）也沒能證明出來。在20世紀之前，人們處在驗證這個猜想階段，沒人能夠證明它。1900年，希爾伯特（Hilbert）在國際數(shù)學家大會的報告中將這個猜想列入他的23個數(shù)學問題之中。1938年華羅庚證明了：“幾乎所有的偶數(shù)都能表示成兩個素數(shù)之和。”如果把命題“任一充分大的偶數(shù)都可以表示成為一個素因子個數(shù)不超過個的數(shù)與另一個素因子不超過b個的數(shù)之和”記作“”，1957年，王元證明了“2+3”。潘承洞在1962年證明了“1+5”。1963年，潘承洞、巴爾巴恩（BapoaH）與王元又都證明了“1+4”（[13]）。1973年陳景潤用新的加權篩法證明了“1+2”（陳氏定理[3]）。除了上述猜想以外，應用科學中也有很多有關素數(shù)的難題：在對信息進行加密的過程中，會應用到大素數(shù)，然而高效率的判斷一個很大的數(shù)（例如一個十進制下一百位的數(shù)）是否為素數(shù)是一個難題，一方面，人們試圖去尋找能夠表示所有素數(shù)的素數(shù)通項公式，因為只要能找到這樣的通項公式，那么尋找素數(shù)、判斷素數(shù)將不再是難事，例如如下的素數(shù)公式：,A對于任意的自然數(shù)m、n都是素數(shù)（公式的原理及詳細證明見[15]），但是利用這個公式來尋找素數(shù)效率很低,因為經(jīng)常取不同的m、n會得到相同的素數(shù)A，且在一定條件下m、n并不是獨立的。另一方面，人們通過尋找素性檢驗算法來判斷給定的數(shù)是否為素數(shù)（詳見4.1），在2004年Agrawal、Kayal和Saxena做出了具有劃時代意義的貢獻，他們給出了一個多項式時間復雜度的確定性算法來測試一個數(shù)是否為素數(shù)（[1]）。在在多項式理論中，類似的問題就是判斷一個給定的多項式是否是不可約多項式。由于不可約性與多項式所在數(shù)域有關，所以要分數(shù)域進行討論。在有限域中，因為小于給定次數(shù)的多項式是有限多個，所以我們可以通過一個個試除的方式，判定一個多項式的不可約性，更高效的方法見[16]。由代數(shù)基本定理，復數(shù)域中的不可約多項式均是一次多項式，實數(shù)域中的不可約多項式均是一次或二次多項式。因此研究重點落在了有理數(shù)域和整數(shù)環(huán)上。艾森斯坦（Eisenstein）判別法算是一座里程碑，奠定了不可約判別法的基礎，它還有許多衍生的判別法（[17]）。另一種常用方法是進行模p約化處理，多項式經(jīng)模p約化得到對應的模p約化多項式（詳見4.2），模p約化多項式所在域為有限域，因此能夠簡化判斷的難度。雖然對于不可約多項式的研究已經(jīng)有很多，但至今都沒有一個可適應所有多項式判定的方法。在本文中，我們所討論的多項式都是一元多項式，判斷的是一元多項式的不可約性，但是我們對于一元多項式中的許多定義，不可約性判定方法都可以推廣到多元多項式中，例如[4]中詳細介紹了如何將一元多項式不可約性判定方法推廣到二元多項式中。

本文的主要內(nèi)容是：定理2.2.1：（多項式的算術基本定理）：對任意域F上的多項式，其中，均有（**），由唯一確定。其中取遍域F上所有的首一不可約多項式，c是的首項系數(shù)，是一個從域F上所有不可約多項式集合映到自然數(shù)集合的函數(shù)，且只在有限多個處取值不為0（因此（**）式右端的乘積為有限乘積）。本文的主要結構是：第二章闡述數(shù)論中算術基本定理的證明過程，將其推廣到多項式理論中，得到域上的一元多項式的算術基本定理。第三章闡述素數(shù)的一些重要性質(zhì)，以及在不可約多項式情形下的推廣。例如證明了不可約多項式有無窮多個。

第四章介紹了幾種素性檢驗方法，并論述了相應的不可約多項式判定的研究背景和具有代表性的判別方法。算術基本定理及其在多項式情形下的推廣2.1算術基本定理算術基本定理又稱為素數(shù)唯一分解定理，是數(shù)論中最重要的定理之一，由它的名稱也可窺得一二，顧名思義關于算術的基本定理，能被稱為是基本定理的定理對于整個數(shù)論來說肯定至關重要。在介紹算術基本定理之前，我們先來回顧一下什么是素數(shù)，不能被因式分解的正整數(shù)叫素數(shù)，換句話說就是若一個大于1的正整數(shù)p，1和p自身是p的所有正因數(shù)（、b是整數(shù)，且b不為0，如果存在整數(shù)c使得，則稱b整除，同時稱b是的一個因數(shù)。如果b大于0，稱b為的一個正因數(shù)。由定義，我們?nèi)菀椎贸觯瑢θ我庹麛?shù)，1和自身都是的正因數(shù)。如果整數(shù),b除了外無其它相同的因數(shù)，則稱,b互素。），則稱p是素數(shù)。例如：29、31、37這樣的數(shù)都是素數(shù)，因為它們除了1和它本身之外沒有其它正因數(shù)。而像6、21、35這樣的數(shù)它們可以進行因式分解：6=23、21=37、35=57，所以6有正因數(shù)2，21有正因數(shù)3，35有正因數(shù)5，所以它們不是素數(shù)，稱之為合數(shù)，另外，1既不是素數(shù)也不是合數(shù)。定理2.1.1（算術基本定理）：任意正整數(shù)都可以唯一表示為素數(shù)的乘積（其中1看作零個素數(shù)的乘積）。我們通過例子來理解這個定理，例如：考慮450，我們可以將450進行因式分解450=23355，唯一性是指只有素數(shù)2、3、5可將450進行分解，無其他素數(shù)，且指數(shù)1、2、2由450唯一決定。如果我們使用符號：（*），其中p取遍所有素數(shù)；為非負整數(shù)，是一個從所有素數(shù)組成的集合映射到自然數(shù)集合的函數(shù)，且只在有限多個p處取值不為0（因此（*）右端為有限乘積）。因此定理2.1.1表述為：任意正整數(shù)n可表示為，其中指數(shù)由n唯一確定。那么具體是什么呢？我們定義函數(shù)：如果，則。另外，若，則例如：則。之后我們可以證明。定理2.1.1看上去表述的很簡單明了，但證明卻不簡單。我們需要介紹一些結論來作為證明的工具（以下證明思路參考了文[6]第一章的內(nèi)容）。以下引理證明了定理2.1.1中表示的存在性。引理2.1.2：任意正整數(shù)n都可以寫成素數(shù)的乘積（其中1看作零個素數(shù)的乘積）證明：我們通過對n歸納來證明：當n=1時，1看作零個素數(shù)的乘積，成立。當n=2時，2本身是素數(shù)，成立。假設我們已經(jīng)證明的命題，則當n=k+1時，若n為素數(shù)，命題成立。若n為合數(shù)，則n可因式分解為，且，則，由歸納假設可寫成素數(shù)的乘積，所以n可寫為素數(shù)的乘積。綜上命題得證。證明定理2.1.1的唯一性不像存在性那么簡單，我們需要如下結論，這些結論看似顯然，但對這樣“顯然的結論”的證明卻是并不可少的。有關這些結論的證明可參見[5]引理2.1.3（整數(shù)的帶余除法）：設,b是整數(shù)，且b大于0,則存在整數(shù)q,r，使得=qb+r,0r<b,且q,r是唯一的。引理2.1.4：如果整除bc，且,b互素，則整除c。由引理2.1.4我們得到兩個推論，這兩個推論是證明定理2.1.1唯一性的關鍵。推論2.1.5：若p是素數(shù)，p整除b，則p整除或p整除b。（注：在抽象代數(shù)中，這相當于說不可約元是素元，這等價于說相應的整環(huán)是唯一因子分解整環(huán)[19]）。推論2.1.6：若p是素數(shù)，,b是整數(shù)，則。有了以上內(nèi)容作為工具，我們就可以證明定理2.1.1的唯一性了：使用函數(shù)作用于等式兩邊，由推論2.1.6函數(shù)的性質(zhì)可得：，又，因此等式右邊=，也就是說，因此唯一性得到證明，且。綜合以上，定理2.1.1的存在性和唯一性都得到證明。例1：將194040化為（*）式的形式。解：將194040進行因式分解：，因此，其中p取遍所有素數(shù)，且。2.2（一元）多項式的情形我們可以將算術基本定理平行推廣到（一元）多項式理論中，得到（一元）多項式的基本定理。在討論此定理之前，同樣的，我們先回顧一下什么是不可約多項式。域F上不能被因式分解的非常數(shù)多項式叫做不可約多項式，換句話說對于域F上的非常數(shù)多項式p(x)，常數(shù)或常數(shù)倍的p(x)是p(x)的所有因式，（域F上的多項式f(x)、g(x)，且g(x)不為零多項式，如果存在域F上的多項式q(x)，使得f(x)=q(x)g(x)，則稱g(x)整除f(x)，且g(x)是f(x)的一個因式。如果f(x)、g(x)除了域F中的常數(shù)外無其他相同的因式，則稱f(x)、g(x)互素。）則稱p(x)為域F上的不可約多項式。例如：是實數(shù)域上的不可約多項式，因為它們除了實數(shù)或?qū)崝?shù)倍的自身，無其他因式。而像它們可以因式分解為、，所以、有因式，所以它們不是實數(shù)域上的不可約多項式。我們稱首項系數(shù)為1的多項式為首一多項式，任意非零多項式可寫成常數(shù)倍的首一多項式。例如：我們可以寫成，其中是首一多項式。設p(x)是域F上的不可約多項式，定義數(shù)：如果則（注：若）定理2.2.1：（多項式的算術基本定理）：對任意域F上的多項式，其中，均有（**），由唯一確定。其中取遍域F上所有的首一不可約多項式，c是的首項系數(shù)，是一個從域F上所有不可約多項式集合映到自然數(shù)集合的函數(shù)，且只在有限多個處取值不為0（因此（**）式右端的乘積為有限乘積）。我們沿用整數(shù)算術基本定理的證明途徑來證明上述定理，以下引理證明了定理2.2.1中（**）式的存在性。引理2.2.2：域F上的非常數(shù)多項式可以寫成不可約多項式的乘積。證明：任取域F上的非常數(shù)多項式，設，則由是非常數(shù)多項式，。下面對n作數(shù)學歸納法：首先當n=1，為不可約多項式，命題成立。現(xiàn)設對的任意次數(shù)為n的多項式，都可以寫成不可約多項式的乘積。則n=k+1時：當k+1次多項式為不可約多項式時，命題成立。當k+1次多項式為可約多項式時，，且，所以，可寫成不可約多項式的乘積，因此可寫成不可約多項式的乘積。綜上，命題得證。為了證明定理2.2.1的唯一性，我們需要如下結論：（以下引理2.2.3、2.2.4分別是引理2.1.2、2.1.3的推廣）引理2.2.3（多項式的帶余除法）：設f(x),g(x)是域F上的兩個多項式，且g(x)不為零多項式，則存在域F上的兩個多項式q(x)、r(x)，使得f(x)=q(x)g(x)+r(x)，r(x)=0或deg(r(x))<deg(g(x))，且q(x),r(x)由f(x),g(x)唯一確定。引理2.2.4：如果f(x)整除g(x)h(x)，且f(x)、g(x)互素，則f(x)整除h(x)。由引理2.2.4我們得到兩個推論，這兩個推論是證明定理2.2.1唯一性的關鍵。推論2.2.5：若p(x)為域F上的不可約多項式，且p(x)整除f(x)g(x)，則p(x)整除f(x)或p(x)整除g(x)。推論2.2.6：設p(x)為域F上的首一不可約多項式，f(x)、g(x)是域F上的多項式，則。有了以上內(nèi)容作為工具，我們就可以證明定理2.2.1的唯一性了：用作用于兩邊，由推論2.2.6我們能夠得到：，因為c為常數(shù)，所以，，所以，因此指數(shù)唯一確定。因為為域F上的首一不可約多項式，所以c為的首項系數(shù)，因此c也由唯一確定。定理2.2.1的唯一性得到證明。例2：在有理數(shù)域上分解多項式。解：首先易知、因此、為的因式且是有理數(shù)域上的不可約多項式，所以可由、表示為，又在有理數(shù)域上是不可約多項式，因此可表示為，其中。第三章素數(shù)的性質(zhì)及其在多項式情形下的推廣定理3.1：素數(shù)有無窮多個。素有“幾何之父”之稱的古希臘學者歐幾里得（Euclid）在《幾何原本》中給出了該定理的證明，因此該定理又稱為歐幾里得定理（Euclidtheorem）。這個定理雖然表述很簡單，但卻魅力無窮，吸引了很多數(shù)學家，在歐幾里得（Euclid）后給出了數(shù)以百計的證明方法。盧昌海在文章[9]中總結了九種比較具有代表性的證明方法。由于歐幾里得（Euclid）的證明方法簡單而歷久彌新，可以說是反證法的范例，歐拉（Euler）的證明則是一個美妙的證明。因此，以下我們只引述歐幾里得（Euclid）和歐拉（Euler）的證明。歐幾里得（Euclid）的證明：反證：設只有有限多個素數(shù)，記作，，,,令，顯然，所以N不是素數(shù)，又N不為1，所以N是合數(shù)，由算數(shù)基本定理可知，存在素數(shù)整除N，然而，矛盾，所以有無窮多個素數(shù)。下面這個證明由歐拉（Euler）給出，它展示了用分析的工具來解決數(shù)論中的問題，被視為解析數(shù)論的開端：設，，,是所有小于等于n的素數(shù)，定義。因為=1++++，所以=（3.1）。由算數(shù)基本定理，任意m小于等于n，m可以寫成，，,的乘積，即中必然會出現(xiàn)在（3.1）右邊的某一項中，（），所以素數(shù)有無窮多個。又==2，所以。于是通過歐拉的證明我們不僅能夠得到有無窮多個素數(shù)且所有素數(shù)的倒數(shù)和發(fā)散。我們知道了素數(shù)有無窮多個，那么這些素數(shù)是如何分布的？素數(shù)的分布規(guī)律一直困擾著數(shù)學家們，一個一個的看，素數(shù)在自然數(shù)中出現(xiàn)沒有什么規(guī)律，但如果總體的看，素數(shù)竟是有規(guī)律的。如果令是1到x之間的所有素數(shù)，許多數(shù)學家通過實驗發(fā)現(xiàn)：當x越大越趨向于，這就是著名的素數(shù)定理。素數(shù)定理描述的是素數(shù)在自然數(shù)中的分布的漸進情況，被認為是素數(shù)的漸進分布定律。定理3.3：（素數(shù)定理）(),亦即：。(定理的詳細內(nèi)容及不同證明方法參見[11])這一定理是1800年左右法國數(shù)學家勒讓德（Legendre）提出的，數(shù)學王子高斯(Gauss)也未能證明，經(jīng)過100多年時間，在1896年法國數(shù)學家阿達馬（Hadamard）和比利時數(shù)學家普森（Poussin）先后給出獨立的證明。證明用到了復分析和黎曼ζ函數(shù)。此后，許多數(shù)學家都期望找到盡可能簡單的證明或它的初等證明。在1949年，兩位年輕的數(shù)學家——賽爾伯格(Selberg)和愛多士(Erd?s)分別獨立地證明了素數(shù)定理，并且他們給出的是一個完全“初等”的證明，當然證明是復雜的。這一結果轟動了整個數(shù)學界，賽爾伯格由于這項成就及其他工作而獲得了菲爾茲獎，愛多士則與陳省身一起獲得了沃爾夫數(shù)學獎。通過素數(shù)定理我們也能夠得到素數(shù)有無窮多個，雖然有點大材小用，而且通過素數(shù)定理我們可以給出關于第n個素數(shù)的漸進估計：，同時，該定理也給出了從自然數(shù)中抽取素數(shù)的概率：從小于等于n的自然數(shù)中隨機的抽取一個數(shù)，它是素數(shù)的概率是。與第二章相同，我們可以將素數(shù)的性質(zhì)推廣到多項式環(huán)境中，得到不可約多項式的性質(zhì)。定理3.4：域F上的不可約多項式有無窮多個。證明：若p(x)為域F上的不可約多項式，任取c為域F中的非零常數(shù)，則cp(x)也為不可約多項式，因此我們可以討論首一不可約多項式。設只有有限多個首一不可約多項式，記為，令，因為整除但是不整除1，所以不整除則，所以不是不可約多項式，又，則是可約多項式，由多項式的算數(shù)基本定理，存在整除，矛盾。所以，域F上的首一不可約多項式有無窮多個。素數(shù)定理告訴我們素數(shù)的漸進分布規(guī)律，那么在有限域上的不可約多項式有沒有什么分布規(guī)律呢？我們在尋找有限域上的m次首一不可約多項式時，需要考慮隨機選取的多項式是不可約多項式的可能性有多大：設為中的m次首一不可約多項式的個數(shù)，則（詳見[12]）而為m次首一多項式的總數(shù)，故當m充分大時，隨機給出一個m次首一多項式是不可約多項式的概率大致為。第四章素性檢驗及不可約多項式的判定4.1幾種素性檢驗方法1.埃拉托斯特尼（Eratosthenes）篩法：將從1開始的給定范圍內(nèi)的正整數(shù)按從小到大的順序排列，逐步篩掉非素數(shù)，直到篩子為空時結束，則留下的數(shù)為素數(shù)。我們通過一個例子來具體說明篩法的使用過程。例3：任意給定一個正整數(shù)30，如圖4-1按從小到大的順序列出1到30的所有的數(shù)；第一步：因為1不是素數(shù)，所以把1劃掉，即劃去圖4-1中綠色的數(shù)字；第二步：1后面的第一個數(shù)是2，2是素數(shù)，保留2，劃掉所有2的倍數(shù)：4、6、8、10、12、14、16、18、20、22、24、26、28、30，即劃去圖4-1中紅色的數(shù)字；第三步：從2往后找，找到第一個未被劃去的數(shù)是3，保留3，劃掉所有3的倍數(shù)：9、15、21、27，即劃去圖4-1中黃色的數(shù)字；第四步：從3往后找，找到第一個未被劃去的數(shù)是5，保留5，劃掉所有5的倍數(shù)：25，即劃去圖4-1中藍色的數(shù)字；第五步：從5往后找，找到第一個未被劃去的數(shù)是7，保留7，劃掉所有7的倍數(shù)，可以看到，已經(jīng)沒有這樣的數(shù)了，篩子為空；第六步：結束篩選，將所有保留的數(shù)列出：2、3、5、7、11、13、17、19、23、29，即圖4-1中灰色底的數(shù)字即為30以內(nèi)的所有素數(shù)。2357111317192329（圖4-1）在我們用此篩法過程中，篩除某個素數(shù)n的倍數(shù)時，已經(jīng)被作為小于該素數(shù)的數(shù)的倍數(shù)篩掉了，因此，倍數(shù)應從開始篩除，所以在之前的這些數(shù)中已經(jīng)沒有任何可以被小于或等于n的數(shù)整除的數(shù)了，這就保證了之前剩下的數(shù)都為素數(shù)。所以當我們用篩法來尋找1到n的所有素數(shù)時，只需要嘗試篩除2到之間的所有整數(shù)的倍數(shù)即可。由此我們得到了以下的試除法。2.試除法：主要是嘗試從2到的整數(shù)是否整除n來檢驗n是否為素數(shù)，若通過檢驗，則n是素數(shù)，這是一種確定性檢驗。這里需要試除([]-1)次，當n特別大時，需要試除的次數(shù)非常多，且其中有些數(shù)不需要挨個試除，因此，此算法效率非常低。例4：檢驗53是否為素數(shù)。解：首先，所以我們只需嘗試從2到7是否整除53來檢驗53是否為素數(shù)，又2不整除53，3不整除53，4不整除53，5不整除53，6不整除53，7不整除53，因此，53通過檢驗，所以53是素數(shù)。3.費馬素性檢驗：根據(jù)費馬小定理：任意的素數(shù)p,任意的,(,p)=1,有，如果我們想知道n是否為素數(shù)，我們從中間選取小于等于n-1的正整數(shù),看看是否滿足等式，若存在不成立，則n是合數(shù)，若對于很多個都能使等式成立，則n很有可能是素數(shù)。（Carmichael數(shù)除外，最小的Carmichael數(shù)是561，Carmichael數(shù)有無窮多個）這是一種概率性檢驗。例5：利用費馬素性檢驗，檢測17是否為素數(shù)。解：任意選取小于等于16的正整數(shù),不妨取=2，（2，17）=1，；=3，（3，17）=1，；=4，（4，17）=1，；=6，（6，17）=1，；=8，（8，17）=1，；存在很多個使得等式成立，因此17極有可能是素數(shù)。4.AKS素性測試：以下算法引自[1]算法如下：輸入正整數(shù)n>1；如果n能夠表示成，則n不是素數(shù)；尋找最小的r，使得（這里是以2為底的對數(shù)）；如果對于一些，有1<(a,n)<n，則n是合數(shù)；如果，則n是素數(shù)；當,如果則n是合數(shù)，否則n是素數(shù)。流程圖如下：輸入n(>1)n=YESNO輸出n不是素數(shù)尋找最小的r,，有1<(a,n)<nYESNO輸出n不是素數(shù)NOYES到輸出n是素數(shù)YES輸出n不是素數(shù)輸出n是素數(shù)例6：用ASK素性測試算法來證明7是素數(shù)。(這個例子并沒有涉及AKS算法的核心部分)證明：因為，所以不存在使得；接下來我們需要尋找最小的r，使得，又，所以。當r=1時，（7，1）=1，不存在正整數(shù)k使得（舍去），當r=2時，（7，2）=1，（舍去），當r=3時，（7，3）=1，（舍去），當r=4時，（7，4）=1，（舍去），當r=5時，（7，5）=1，（舍去），當r=6時，（7，6）=1，（舍去），當r=7時，（7，7）=7（舍去），當r=8時，（7，8）=1，（舍去），當r=9時，（7，9）=1，（舍去），當r=10時，（7，10）=1，（舍去），當r=11時，（7，11）=1，（成立），所以r=11;任意的正整數(shù)；又，所以7是素數(shù)。在多項式中，我們也在尋找有理數(shù)域和整數(shù)環(huán)上的不可約多項式的判定方法。如果是有理數(shù)域Q上的非零多項式，我們?nèi)≌麛?shù)c,使得為整數(shù)，取,則是整數(shù)環(huán)上的本原多項式（關于本原多項式的定義及證明參見[5]）。因此，有理數(shù)域上的任意非零多項式都對應整數(shù)環(huán)上的一個本原多項式。如果，其中為非零有理數(shù)，為對應的本原多項式，則。又為本原多項式，則。因此從本質(zhì)上來說，此對應是唯一的。所以，對于有理數(shù)域上多項式的不可約問題，我們可以簡化為討論整數(shù)環(huán)上的多項式的不可約問題。判斷一個整系數(shù)多項式是否可約是很困難的，其中最為經(jīng)典的判別法是艾森斯坦（Eisenstein）判別法，另一個著名手法是模p約化法，通過模p約化簡化多項式，使我們能容易的判斷其不可約性。當然，還有許多其他的判別方法，以及一些對于特殊形式的多項式的判別法，但是到目前為止，還沒能找到一個通用的判別方法適應所有的多項式。4.2整系數(shù)多項式不可約性常用判別法1.艾森斯坦（Eisenstein）判別法：設是整系數(shù)多項式，若存在素數(shù)p，使得：①p，②，③，則在整數(shù)環(huán)Z上不可約（有理數(shù)域Q上也不可約）。下面我們通過舉例來運用此判別方法，在實際問題中有時需要通過轉(zhuǎn)化來間接運用此判別法，而文章[18]告訴我們一類不能運用此判別法的多項式，表明此判別法并不適應所有的多項式。例7：證明，在有理數(shù)域Q上不可約。證明：取p=3,則，由艾森斯坦判別法在Q上不可約。2.模p約化法：設為整系數(shù)多項式，將模p（p是素數(shù)），得到對應的，即將它們的系數(shù)對應所屬的模p同余類，稱為的模p約化多項式。我們有結論：若整系數(shù)多項式的模p約化多項式在上為不可約多項式，則在整數(shù)環(huán)上不可約（在有理數(shù)域也不可約）。反之不成立。例8：證明為有理數(shù)域上的不可約多項式。證明：取p=5，得的模5約化多項式，易知為上的不可約多項式，所以由模p判別法知為有理數(shù)域上的不可約多項式。4.3在有限域上尋找不可約多項式通過篩法我們可以找到給定范圍內(nèi)的素數(shù)，那么在有限域中我們能否尋找給定次數(shù)的不可約多項式？設是一個有限域，若在有限