算法數(shù)論概要課件

算法數(shù)論算法數(shù)論10算法數(shù)論概述算法數(shù)論研究數(shù)論中提出問題的算法（包括并行算法，有時(shí)也包括計(jì)算機(jī)結(jié)構(gòu)），例如：素性檢測(cè)、整數(shù)因子分解和離散對(duì)數(shù)問題等是一門融合數(shù)論和計(jì)算機(jī)科學(xué)的跨專業(yè)、跨領(lǐng)域的學(xué)科。目的：設(shè)計(jì)出有效的計(jì)算機(jī)算法（有時(shí)是高速的計(jì)算機(jī)結(jié)構(gòu)）用于數(shù)論中大規(guī)模數(shù)值計(jì)算（包括驗(yàn)證）。0算法數(shù)論概述算法數(shù)論研究數(shù)論中提出問題的算法（包括并行2研究內(nèi)容素性檢測(cè)

1.素性檢測(cè)最快的確定性算法是APRCL算法，該算法是由Adleman、Pomerance、Rumely、Cohen和Lenstra發(fā)明的，運(yùn)行時(shí)間是該算法有可能在相對(duì)合理的時(shí)間內(nèi)檢測(cè)出1000位整數(shù)的素性。2.目前最有實(shí)用價(jià)值的素性檢測(cè)/證明算法是由Atkin和Morain設(shè)計(jì)的橢圓曲線素性檢測(cè)算法ECPP,該算法可在合理的時(shí)間內(nèi)，如在數(shù)周工作站時(shí)間內(nèi)檢測(cè)出幾千位整數(shù)的素性。研究內(nèi)容3整數(shù)因子分解最快的一般性算法是數(shù)域篩法（NFS），該算法在合理假設(shè)的期望下的運(yùn)行時(shí)間為

顯然，NFS不是多項(xiàng)式時(shí)間算法，而是亞指數(shù)時(shí)間算法。NFS分解的最大整數(shù)是一個(gè)155位的整數(shù)：RSA-155（1999年5月）。

整數(shù)因子分解4離散對(duì)數(shù)問題（有限域上的）乘法群上的離散對(duì)數(shù)問題（DLP）與整數(shù)因子分解問題類似（更難些），而且整數(shù)因子分解方法（例如數(shù)域篩法）通常也適用于離散對(duì)數(shù)問題。注：盡管目前沒有人知道是否能知道出適用的量子計(jì)算機(jī)，但目前已有量子算法可以通過量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決整數(shù)因子分解問題和離散對(duì)數(shù)問題。離散對(duì)數(shù)問題（有限域上的）5橢圓曲線離散對(duì)數(shù)問題

令是定義在有限域上的橢圓曲線，是E上的兩個(gè)點(diǎn)。橢圓曲線離散對(duì)數(shù)問題（ECDLP）是要找一個(gè)整數(shù)k使得在有Q=kP成立。當(dāng)p很大時(shí)該問題被認(rèn)為是個(gè)非常困難的問題，基于這個(gè)原因，ECDLP已成為幾種不同密碼體制的基礎(chǔ)?，F(xiàn)在已有像數(shù)域篩法這樣的亞指數(shù)復(fù)雜度的指數(shù)演算法來接有限域上的離散對(duì)數(shù)問題，但還沒找到有效的指數(shù)演算法來解橢圓曲線離散對(duì)數(shù)問題；而且，ECDLP問題可能沒有指數(shù)演算法。目前對(duì)ECDLP的研究重點(diǎn)在于設(shè)計(jì)像Xedni演算法的新算法來解ECDLP。橢圓曲線離散對(duì)數(shù)問題6梅森素?cái)?shù)

迄今為止找到的梅森素?cái)?shù)有47個(gè)，2008年8月，美國加州大學(xué)洛杉磯分校(UCLA)的計(jì)算機(jī)專家史密斯（E.Smith）通過參加一個(gè)名為“因特網(wǎng)梅森素?cái)?shù)大搜索”(GIMPS)的國際合作項(xiàng)目，發(fā)現(xiàn)了第46個(gè)也是目前最大的梅森素?cái)?shù)：，它大約有1300萬位數(shù)(準(zhǔn)確地說，是12978189位數(shù))，如果用普通字號(hào)將這個(gè)巨數(shù)連續(xù)寫下來，它的長度可超過50公里!最近，這一成就被美國的《時(shí)代》雜志評(píng)為“2008年度50項(xiàng)最佳發(fā)明”之一，排名在第29位。梅森素?cái)?shù)的意義和價(jià)值是發(fā)現(xiàn)已知最大素?cái)?shù)的最有效途徑；它的探究推動(dòng)了數(shù)學(xué)皇后——數(shù)論的研究，促進(jìn)了計(jì)算技術(shù)、程序設(shè)計(jì)技術(shù)、密碼技術(shù)的發(fā)展以及快速傅立葉變換的應(yīng)用。探尋梅森素?cái)?shù)最新的意義是：它促進(jìn)了網(wǎng)格技術(shù)的發(fā)展。而網(wǎng)格技術(shù)將是一項(xiàng)應(yīng)用非常廣闊、前景十分誘人的技術(shù)。探尋梅森素?cái)?shù)的方法還可用來測(cè)試計(jì)算機(jī)硬件運(yùn)算是否正確。由于探尋梅森素?cái)?shù)需要多種學(xué)科和技術(shù)的支持，所以許多科學(xué)家認(rèn)為：梅森素?cái)?shù)的研究成果，在一定程度上反映了一個(gè)國家的科技水平。英國頂尖科學(xué)家索托伊(M.Sautoy)甚至認(rèn)為它是標(biāo)志科學(xué)發(fā)展的里程碑。梅森素?cái)?shù)7奇完全數(shù)偶完全數(shù)和梅森素?cái)?shù)有一一對(duì)應(yīng)關(guān)系，即，只要找到一個(gè)梅森素?cái)?shù)就有一個(gè)偶完全數(shù)已知的完全數(shù)都是偶數(shù)，尚不知是否存在奇完全數(shù)，數(shù)據(jù)結(jié)果顯示沒有比小的奇完全數(shù)。費(fèi)馬數(shù)現(xiàn)在只發(fā)現(xiàn)了前5個(gè)費(fèi)馬數(shù)(即，n=0,1,2,3,4)是素?cái)?shù)，其余的費(fèi)馬數(shù)或者是合數(shù)，或者素性未知。計(jì)算素?cái)?shù)個(gè)數(shù)最新紀(jì)錄：=783964159852157952242,即,不超過的素?cái)?shù)恰有783964159852157952242個(gè)…….

奇完全數(shù)8計(jì)算可行性算法數(shù)論注重?cái)?shù)論的算法方面且以設(shè)計(jì)出能解決各類數(shù)論問題的有效算法為目標(biāo)從實(shí)際可計(jì)算角度，可將算法分為兩類：有效(好的)算法：可在多項(xiàng)式時(shí)間內(nèi)運(yùn)行完的算法無效(壞的)算法：只能在指數(shù)時(shí)間內(nèi)運(yùn)行完的算法下列兩個(gè)問題是計(jì)算難處理的素性檢測(cè)問題整數(shù)因子分解問題計(jì)算可行性算法數(shù)論注重?cái)?shù)論的算法方面且以設(shè)計(jì)出能解決各類數(shù)論91素性檢測(cè)算法素性檢測(cè)問題（PTP）可描述成如下簡單判定問題：輸入：大于1的整數(shù)n輸出：是，若n為素?cái)?shù)否，其他理論上：驗(yàn)證n能否被2~n/2的任何整數(shù)整除

1素性檢測(cè)算法素性檢測(cè)問題（PTP）可描述成如下簡單判定問10判定問題(Decisionproblem)：只能回答“是”或“否”的問題。隨機(jī)算法：使用了隨機(jī)數(shù)的算法。確定性算法：沒有使用隨機(jī)數(shù)的算法。對(duì)一個(gè)判定問題的一個(gè)偏“是”的(yes-biased)MonteCarlo算法是具有下列性質(zhì)的一個(gè)隨機(jī)算法：一個(gè)“是”回答總是正確的，但一個(gè)“否”回答也許是不正確的。

一個(gè)偏“是”的MonteCarlo算法具有錯(cuò)誤概率：如果算法對(duì)任何回答應(yīng)該為“是”的實(shí)例至多以的概率給出不正確的回答“否”（該概率是對(duì)于給定輸入算法在所有可能的隨機(jī)選擇上計(jì)算而得）判定問題(Decisionproblem)：只能回答“是”11在建立RSA密碼體制過程中，必須生成大的“隨機(jī)素?cái)?shù)”，方法：先生成大的隨機(jī)整數(shù)，然后檢測(cè)他們的素性。2002年，Agrawal，kayal和Saxena證明了存在一個(gè)素性檢測(cè)的多項(xiàng)式時(shí)間確定性算法。實(shí)際應(yīng)用中，素性檢測(cè)仍只要利用隨機(jī)多項(xiàng)式時(shí)間MonteCarlo算法，例如：Solovay-Strassen算法或Miller-Rabin算法（它們很快，但有一定的概率可能將一個(gè)合數(shù)斷言為素?cái)?shù)）在建立RSA密碼體制過程中，必須生成大的“隨機(jī)素?cái)?shù)”，方法：122000多年以前古希臘數(shù)學(xué)家愛拉托散特尼發(fā)現(xiàn)一種找出質(zhì)數(shù)的方法稱為愛拉托散特尼篩法

方法如下：1不是質(zhì)數(shù)去掉。2是質(zhì)數(shù)留下，之后所有2的倍數(shù)皆刪掉。3沒刪掉是質(zhì)數(shù)留下，之后所有3的倍數(shù)皆刪掉。4已經(jīng)刪掉，5沒刪掉是質(zhì)數(shù)留下，之后所有5的倍數(shù)皆刪掉。6已經(jīng)刪掉，7沒刪掉是質(zhì)數(shù)留下，之后所有7的倍數(shù)皆刪掉?！来祟愅萍纯烧页鏊匈|(zhì)數(shù)。2000多年以前古希臘數(shù)學(xué)家愛拉托散特尼發(fā)現(xiàn)一種找出質(zhì)數(shù)的方13200以內(nèi)的素?cái)?shù):

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199200以內(nèi)的素?cái)?shù):141.1確定性的嚴(yán)格素性檢測(cè)1.1.1試除法若n沒有不超過的素因子，則n為素?cái)?shù)。該法只須用2~[]之間的素?cái)?shù)（可由埃拉托色尼篩法或使用含有之前素?cái)?shù)的素?cái)?shù)表得到）來整除n。運(yùn)算量：對(duì)于大整數(shù)的素性檢測(cè)，并非完全實(shí)際有效。1.1確定性的嚴(yán)格素性檢測(cè)1.1.1試除法15對(duì)于大數(shù)的素性檢驗(yàn)來說沒有簡單直接的方法，本節(jié)介紹兩種概率檢驗(yàn)法，均為偏“是”的MonteCarlo算法一、Miller-Rabin算法1.2素性檢驗(yàn)的概率算法對(duì)于大數(shù)的素性檢驗(yàn)來說沒有簡單直接的方法，本節(jié)介紹兩種概率檢16引理:如果p為大于2的素?cái)?shù)，則方程x2≡1(modp)的解只有x≡1和x≡-1。證明：由x2≡1modp，有x2-1≡0modp，(x+1)(x-1)≡0modp，因此p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)。若p|(x+1)且p|(x-1)，則存在兩個(gè)整數(shù)k和j，使得x+1=kp，x-1=jp,兩式相減得2=(k-j)p，為不可能結(jié)果。所以有p|(x+1)或p|(x-1)。設(shè)p|(x+1)，則x+1=kp，因此x≡-1(modp)。類似地可得x≡1(modp)。（證畢）引理:如果p為大于2的素?cái)?shù)，則方程x2≡1(modp)17引理的逆否命題為：如果方程x2≡1modp有一解x0{-1,1}，那么p不為素?cái)?shù)。

例如：考慮方程x2≡1(mod8)由Z8上模乘法的結(jié)果得12≡1mod8,32≡1mod8,52≡1mod8,72≡1mod8又5≡-3mod8，7≡-1mod8，所以方程的解為1，-1，3，-3，可見8不是素?cái)?shù)。引理的逆否命題為：如果方程x2≡1modp有一解x0{18Miller-Rabin的素性概率檢測(cè)法。首先將n-1表示為二進(jìn)制形式bkbk-1…b0，并給d賦初值1，隨機(jī)選擇整數(shù)a，使得a介于1~n-1，則算法Witness(a,n)的核心部分如下：fori=kdownto0do { x←d; d←(d×d)modn; ifd=1and(x≠1)and(x≠n-1)thenreturnFalse; ifbi=1thend←(d×a)modn }ifd≠1thenreturnFalse;returnTrue.Miller-Rabin的素性概率檢測(cè)法。19

此算法有兩個(gè)輸入?yún)?shù)，n是待檢驗(yàn)的數(shù)，a是小于n的整數(shù)。如果算法的返回值為False，則n肯定不是素?cái)?shù)，如果返回值為True，則n有可能是素?cái)?shù)。 for循環(huán)結(jié)束后，有d≡an-1modn，由Fermat定理知，若n為素?cái)?shù)，則d為1。因此若d≠1，則n不為素?cái)?shù)，所以返回False。 因?yàn)閚-1≡-1modn，所以(x≠1)and(x≠n-1),指x2≡1(modn)有不在{-1,1}中的根，因此n不為素?cái)?shù)，返回False。 此算法有兩個(gè)輸入?yún)?shù)，n是待檢驗(yàn)的數(shù)，a是小于n的整數(shù)。20該算法有以下性質(zhì)：對(duì)s個(gè)不同的a，重復(fù)調(diào)用這一算法，只要有一次算法返回為False，就可肯定n不是素?cái)?shù)。如果算法每次返回都為True，則n是素?cái)?shù)的概率至少為1-2-s，因此對(duì)于足夠大的s，就可以非?？隙ǖ叵嘈舗為素?cái)?shù)。Miller-Rabin算法的錯(cuò)誤概率至多為1/4該算法有以下性質(zhì)：對(duì)s個(gè)不同的a，重復(fù)調(diào)用這一算法，只要有211.3利用n-1、n+1的因子分解的素性檢驗(yàn)利用n-1的因子分解的素性檢驗(yàn)費(fèi)馬小定理的盧卡斯反問題（1891）如果存在整數(shù)a，滿足(1)以及(2)對(duì)n-1的每個(gè)素因子p都不成立，則n為素?cái)?shù)。缺陷：需要知道n-1的素因子分解，這是一個(gè)和因子分解n難度差不多的問題，且比對(duì)n進(jìn)行素性檢測(cè)更困難。Pocklintin定理P135Proth定理P135利用n+1的因子分解的素性檢驗(yàn)P1361.3利用n-1、n+1的因子分解的素性檢驗(yàn)利用n-1的因22算法數(shù)論算法數(shù)論230算法數(shù)論概述算法數(shù)論研究數(shù)論中提出問題的算法（包括并行算法，有時(shí)也包括計(jì)算機(jī)結(jié)構(gòu)），例如：素性檢測(cè)、整數(shù)因子分解和離散對(duì)數(shù)問題等是一門融合數(shù)論和計(jì)算機(jī)科學(xué)的跨專業(yè)、跨領(lǐng)域的學(xué)科。目的：設(shè)計(jì)出有效的計(jì)算機(jī)算法（有時(shí)是高速的計(jì)算機(jī)結(jié)構(gòu)）用于數(shù)論中大規(guī)模數(shù)值計(jì)算（包括驗(yàn)證）。0算法數(shù)論概述算法數(shù)論研究數(shù)論中提出問題的算法（包括并行24研究內(nèi)容素性檢測(cè)

1.素性檢測(cè)最快的確定性算法是APRCL算法，該算法是由Adleman、Pomerance、Rumely、Cohen和Lenstra發(fā)明的，運(yùn)行時(shí)間是該算法有可能在相對(duì)合理的時(shí)間內(nèi)檢測(cè)出1000位整數(shù)的素性。2.目前最有實(shí)用價(jià)值的素性檢測(cè)/證明算法是由Atkin和Morain設(shè)計(jì)的橢圓曲線素性檢測(cè)算法ECPP,該算法可在合理的時(shí)間內(nèi)，如在數(shù)周工作站時(shí)間內(nèi)檢測(cè)出幾千位整數(shù)的素性。研究內(nèi)容25整數(shù)因子分解最快的一般性算法是數(shù)域篩法（NFS），該算法在合理假設(shè)的期望下的運(yùn)行時(shí)間為

顯然，NFS不是多項(xiàng)式時(shí)間算法，而是亞指數(shù)時(shí)間算法。NFS分解的最大整數(shù)是一個(gè)155位的整數(shù)：RSA-155（1999年5月）。

整數(shù)因子分解26離散對(duì)數(shù)問題（有限域上的）乘法群上的離散對(duì)數(shù)問題（DLP）與整數(shù)因子分解問題類似（更難些），而且整數(shù)因子分解方法（例如數(shù)域篩法）通常也適用于離散對(duì)數(shù)問題。注：盡管目前沒有人知道是否能知道出適用的量子計(jì)算機(jī)，但目前已有量子算法可以通過量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)解決整數(shù)因子分解問題和離散對(duì)數(shù)問題。離散對(duì)數(shù)問題（有限域上的）27橢圓曲線離散對(duì)數(shù)問題

令是定義在有限域上的橢圓曲線，是E上的兩個(gè)點(diǎn)。橢圓曲線離散對(duì)數(shù)問題（ECDLP）是要找一個(gè)整數(shù)k使得在有Q=kP成立。當(dāng)p很大時(shí)該問題被認(rèn)為是個(gè)非常困難的問題，基于這個(gè)原因，ECDLP已成為幾種不同密碼體制的基礎(chǔ)。現(xiàn)在已有像數(shù)域篩法這樣的亞指數(shù)復(fù)雜度的指數(shù)演算法來接有限域上的離散對(duì)數(shù)問題，但還沒找到有效的指數(shù)演算法來解橢圓曲線離散對(duì)數(shù)問題；而且，ECDLP問題可能沒有指數(shù)演算法。目前對(duì)ECDLP的研究重點(diǎn)在于設(shè)計(jì)像Xedni演算法的新算法來解ECDLP。橢圓曲線離散對(duì)數(shù)問題28梅森素?cái)?shù)

迄今為止找到的梅森素?cái)?shù)有47個(gè)，2008年8月，美國加州大學(xué)洛杉磯分校(UCLA)的計(jì)算機(jī)專家史密斯（E.Smith）通過參加一個(gè)名為“因特網(wǎng)梅森素?cái)?shù)大搜索”(GIMPS)的國際合作項(xiàng)目，發(fā)現(xiàn)了第46個(gè)也是目前最大的梅森素?cái)?shù)：，它大約有1300萬位數(shù)(準(zhǔn)確地說，是12978189位數(shù))，如果用普通字號(hào)將這個(gè)巨數(shù)連續(xù)寫下來，它的長度可超過50公里!最近，這一成就被美國的《時(shí)代》雜志評(píng)為“2008年度50項(xiàng)最佳發(fā)明”之一，排名在第29位。梅森素?cái)?shù)的意義和價(jià)值是發(fā)現(xiàn)已知最大素?cái)?shù)的最有效途徑；它的探究推動(dòng)了數(shù)學(xué)皇后——數(shù)論的研究，促進(jìn)了計(jì)算技術(shù)、程序設(shè)計(jì)技術(shù)、密碼技術(shù)的發(fā)展以及快速傅立葉變換的應(yīng)用。探尋梅森素?cái)?shù)最新的意義是：它促進(jìn)了網(wǎng)格技術(shù)的發(fā)展。而網(wǎng)格技術(shù)將是一項(xiàng)應(yīng)用非常廣闊、前景十分誘人的技術(shù)。探尋梅森素?cái)?shù)的方法還可用來測(cè)試計(jì)算機(jī)硬件運(yùn)算是否正確。由于探尋梅森素?cái)?shù)需要多種學(xué)科和技術(shù)的支持，所以許多科學(xué)家認(rèn)為：梅森素?cái)?shù)的研究成果，在一定程度上反映了一個(gè)國家的科技水平。英國頂尖科學(xué)家索托伊(M.Sautoy)甚至認(rèn)為它是標(biāo)志科學(xué)發(fā)展的里程碑。梅森素?cái)?shù)29奇完全數(shù)偶完全數(shù)和梅森素?cái)?shù)有一一對(duì)應(yīng)關(guān)系，即，只要找到一個(gè)梅森素?cái)?shù)就有一個(gè)偶完全數(shù)已知的完全數(shù)都是偶數(shù)，尚不知是否存在奇完全數(shù)，數(shù)據(jù)結(jié)果顯示沒有比小的奇完全數(shù)。費(fèi)馬數(shù)現(xiàn)在只發(fā)現(xiàn)了前5個(gè)費(fèi)馬數(shù)(即，n=0,1,2,3,4)是素?cái)?shù)，其余的費(fèi)馬數(shù)或者是合數(shù)，或者素性未知。計(jì)算素?cái)?shù)個(gè)數(shù)最新紀(jì)錄：=783964159852157952242,即,不超過的素?cái)?shù)恰有783964159852157952242個(gè)…….

奇完全數(shù)30計(jì)算可行性算法數(shù)論注重?cái)?shù)論的算法方面且以設(shè)計(jì)出能解決各類數(shù)論問題的有效算法為目標(biāo)從實(shí)際可計(jì)算角度，可將算法分為兩類：有效(好的)算法：可在多項(xiàng)式時(shí)間內(nèi)運(yùn)行完的算法無效(壞的)算法：只能在指數(shù)時(shí)間內(nèi)運(yùn)行完的算法下列兩個(gè)問題是計(jì)算難處理的素性檢測(cè)問題整數(shù)因子分解問題計(jì)算可行性算法數(shù)論注重?cái)?shù)論的算法方面且以設(shè)計(jì)出能解決各類數(shù)論311素性檢測(cè)算法素性檢測(cè)問題（PTP）可描述成如下簡單判定問題：輸入：大于1的整數(shù)n輸出：是，若n為素?cái)?shù)否，其他理論上：驗(yàn)證n能否被2~n/2的任何整數(shù)整除

1素性檢測(cè)算法素性檢測(cè)問題（PTP）可描述成如下簡單判定問32判定問題(Decisionproblem)：只能回答“是”或“否”的問題。隨機(jī)算法：使用了隨機(jī)數(shù)的算法。確定性算法：沒有使用隨機(jī)數(shù)的算法。對(duì)一個(gè)判定問題的一個(gè)偏“是”的(yes-biased)MonteCarlo算法是具有下列性質(zhì)的一個(gè)隨機(jī)算法：一個(gè)“是”回答總是正確的，但一個(gè)“否”回答也許是不正確的。

一個(gè)偏“是”的MonteCarlo算法具有錯(cuò)誤概率：如果算法對(duì)任何回答應(yīng)該為“是”的實(shí)例至多以的概率給出不正確的回答“否”（該概率是對(duì)于給定輸入算法在所有可能的隨機(jī)選擇上計(jì)算而得）判定問題(Decisionproblem)：只能回答“是”33在建立RSA密碼體制過程中，必須生成大的“隨機(jī)素?cái)?shù)”，方法：先生成大的隨機(jī)整數(shù)，然后檢測(cè)他們的素性。2002年，Agrawal，kayal和Saxena證明了存在一個(gè)素性檢測(cè)的多項(xiàng)式時(shí)間確定性算法。實(shí)際應(yīng)用中，素性檢測(cè)仍只要利用隨機(jī)多項(xiàng)式時(shí)間MonteCarlo算法，例如：Solovay-Strassen算法或Miller-Rabin算法（它們很快，但有一定的概率可能將一個(gè)合數(shù)斷言為素?cái)?shù)）在建立RSA密碼體制過程中，必須生成大的“隨機(jī)素?cái)?shù)”，方法：342000多年以前古希臘數(shù)學(xué)家愛拉托散特尼發(fā)現(xiàn)一種找出質(zhì)數(shù)的方法稱為愛拉托散特尼篩法

方法如下：1不是質(zhì)數(shù)去掉。2是質(zhì)數(shù)留下，之后所有2的倍數(shù)皆刪掉。3沒刪掉是質(zhì)數(shù)留下，之后所有3的倍數(shù)皆刪掉。4已經(jīng)刪掉，5沒刪掉是質(zhì)數(shù)留下，之后所有5的倍數(shù)皆刪掉。6已經(jīng)刪掉，7沒刪掉是質(zhì)數(shù)留下，之后所有7的倍數(shù)皆刪掉?！来祟愅萍纯烧页鏊匈|(zhì)數(shù)。2000多年以前古希臘數(shù)學(xué)家愛拉托散特尼發(fā)現(xiàn)一種找出質(zhì)數(shù)的方35200以內(nèi)的素?cái)?shù):

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199200以內(nèi)的素?cái)?shù):361.1確定性的嚴(yán)格素性檢測(cè)1.1.1試除法若n沒有不超過的素因子，則n為素?cái)?shù)。該法只須用2~[]之間的素?cái)?shù)（可由埃拉托色尼篩法或使用含有之前素?cái)?shù)的素?cái)?shù)表得到）來整除n。運(yùn)算量：對(duì)于大整數(shù)的素性檢測(cè)，并非完全實(shí)際有效。1.1確定性的嚴(yán)格素性檢測(cè)1.1.1試除法37對(duì)于大數(shù)的素性檢驗(yàn)來說沒有簡單直接的方法，本節(jié)介紹兩種概率檢驗(yàn)法，均為偏“是”的MonteCarlo算法一、Miller-Rabin算法1.2素性檢驗(yàn)的概率算法對(duì)于大數(shù)的素性檢驗(yàn)來說沒有簡單直接的方法，本節(jié)介紹兩種概率檢38引理:如果p為大于2的素?cái)?shù)，則方程x2≡1(modp)的解只有x≡1和x≡-1。證明：由x2≡1modp，有x2-1≡0modp，(x+1)(x-1)≡0modp，因此p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)。若p|(x+1)且p|(x-1)，則存在兩個(gè)整數(shù)k和j，使得x+1=kp，x-1=jp,兩式相減得2=(k-j)p，為不可能結(jié)果。所以有p|(x+1)或p|(x-1)。設(shè)p|(x+1)，則x+1=kp，因此x≡-1(modp)。類似地可得x≡1(modp)。（證畢）引理:如果p為大于2的素?cái)?shù)，則方程x2≡1(modp)39引理的逆否命題為：如果方程x2≡1modp有一解x0{-1,1}，那么p不為素?cái)?shù)。

例如：考慮方程x2≡1(mod8)由Z8上模乘法的結(jié)果得12≡1mod8,32≡1mod8,52≡1mod8,72≡1mod8又5≡-3mod8，7≡-1mod8，所以方程的解為1，-1，3，-3，可見8不是素?cái)?shù)。引理的逆否命題為：如果方程x2≡1modp有一解x0{40Miller-Rabin的素性概率檢測(cè)法。首先將n-1表示為二進(jìn)制形式bkbk-1…b0，并給d賦初值1，隨機(jī)選