一、摘要
????????大數(shù)素性檢測(cè)一直是數(shù)論界、密碼學(xué)界等經(jīng)久不衰的研究方向，實(shí)現(xiàn)大數(shù)素性檢測(cè)的算法也在不斷地被改進(jìn)。目前已經(jīng)出現(xiàn)了很多大數(shù)素性檢測(cè)的算法，而Miller-Rabin算法在其中顯得十分耀眼。本文調(diào)研了常見(jiàn)的大素?cái)?shù)判斷算法，并詳細(xì)介紹了Miller-Rabin大素?cái)?shù)判斷算法的原理，然后結(jié)合相關(guān)的數(shù)論知識(shí)，以生成一個(gè)512bits的大素?cái)?shù)為例，編程實(shí)現(xiàn)了該大素?cái)?shù)判斷算法。
二、引言
i.研究的問(wèn)題及其背景
????????素?cái)?shù)是除了自身和1以外，沒(méi)有其他素?cái)?shù)因子的自然數(shù)。在我們以前的數(shù)學(xué)學(xué)習(xí)過(guò)程中，我們知道了很多素?cái)?shù)。但這些我們認(rèn)知范圍內(nèi)的素?cái)?shù)，無(wú)論是在數(shù)值還是個(gè)數(shù)方面，相對(duì)于整個(gè)素?cái)?shù)集，都是十分受限的。自從歐幾里得證明了有無(wú)窮個(gè)素?cái)?shù)以后，人們就企圖尋找一個(gè)可以構(gòu)造所有素?cái)?shù)的公式，尋找判定一個(gè)自然數(shù)是不是素?cái)?shù)的方法。尤其是對(duì)于一個(gè)數(shù)值很大的數(shù)，要判斷其是否為素?cái)?shù)，單靠直覺(jué)或者查詢相關(guān)素?cái)?shù)表是遠(yuǎn)遠(yuǎn)達(dá)不到我們的期望的。而素?cái)?shù)的應(yīng)用十分廣泛，地位尤其重要，因此確定一個(gè)大數(shù)是否為素?cái)?shù)是數(shù)學(xué)發(fā)展史上一個(gè)無(wú)法回避的問(wèn)題。故而，大素?cái)?shù)的檢測(cè)方法應(yīng)運(yùn)而生，并隨著時(shí)間的推移而快速發(fā)展。
????????素性檢測(cè)可分為兩大類，即確定性素性檢測(cè)和隨機(jī)素性檢測(cè)。前者可給出確定的結(jié)果但通常較慢，后者則與之相反。本篇文章主要介紹三種常見(jiàn)的大素?cái)?shù)判斷算法，并給出Miller-Rabin算法的編程實(shí)現(xiàn)。
ii.研究的目的及其意義
????????素?cái)?shù)在密碼學(xué)中發(fā)揮著十分重要的作用。密碼學(xué)完全是關(guān)于數(shù)論的，所有整數(shù)(0和1除外)都由質(zhì)數(shù)組成，因此在數(shù)論中處理質(zhì)數(shù)很多。素?cái)?shù)被利用在密碼學(xué)上，所謂的公鑰就是將想要傳遞的信息在編碼時(shí)加入質(zhì)數(shù)，編碼之后傳送給收信人，任何人收到此信息后，若沒(méi)有此收信人所擁有的密鑰，則解密的過(guò)程中（實(shí)為尋找素?cái)?shù)的過(guò)程），將會(huì)因?yàn)檎屹|(zhì)數(shù)的過(guò)程（分解質(zhì)因數(shù)）過(guò)久，使即使取得信息也會(huì)無(wú)意義。
????????給出兩個(gè)大素?cái)?shù)，很容易就能將它們兩個(gè)相乘。但是，給出它們的乘積，找出它們的因子就顯得不是那么容易了。這就是許多現(xiàn)代密碼系統(tǒng)的關(guān)鍵所在。如果能夠找到解決整數(shù)分解問(wèn)題的快速方法，幾個(gè)重要的密碼系統(tǒng)將會(huì)被攻破，包括RSA公鑰算法和Blum Blum Shub隨機(jī)數(shù)發(fā)生器。盡管快速分解是攻破這些系統(tǒng)的方法之一，仍然會(huì)有其它的不涉及到分解的其它方法。所以情形完全可能變成這樣：整數(shù)分解問(wèn)題仍然是非常困難，這些密碼系統(tǒng)卻是能夠很快攻破。有的密碼系統(tǒng)則能提供更強(qiáng)的保證：如果這些密碼系統(tǒng)被快速破解（即能夠以多項(xiàng)式時(shí)間復(fù)雜度破解），則可以利用破解這些系統(tǒng)的算法來(lái)快速地（以多項(xiàng)式時(shí)間復(fù)雜度）分解整數(shù)。換句話說(shuō)，破解這樣的密碼系統(tǒng)不會(huì)比整數(shù)分解更容易。這樣的密碼系統(tǒng)包括 Rabin密碼系統(tǒng)（RSA的一個(gè)變體），以及 Blum Blum Shub 隨機(jī)數(shù)發(fā)生器。
????????對(duì)一個(gè)很大的數(shù)進(jìn)行素性判斷，對(duì)于解決整數(shù)分解問(wèn)題是有極大的助推作用的，也是一個(gè)十分關(guān)鍵的環(huán)節(jié)?？梢哉f(shuō)，如果我們能夠首先快速準(zhǔn)確地解決大數(shù)素性檢測(cè)的問(wèn)題，那么才會(huì)有找到解決整數(shù)分解問(wèn)題的快速方法的可能。因此本次研究Miller-Rabin大素?cái)?shù)判斷算法的原理及其實(shí)現(xiàn)是很有實(shí)際意義的。
三、研究方法和研究過(guò)程
????????本次研究，我主要使用了文獻(xiàn)研究法、經(jīng)驗(yàn)總結(jié)法和實(shí)驗(yàn)研究法。首先通過(guò)閱讀大量相關(guān)的文獻(xiàn)，形成對(duì)大素?cái)?shù)判斷算法的科學(xué)認(rèn)識(shí)；然后總結(jié)出前人研究大素?cái)?shù)判斷算法的一些寶貴經(jīng)驗(yàn)，在此基礎(chǔ)上編寫(xiě)代碼并運(yùn)行，根據(jù)運(yùn)行結(jié)果不斷改進(jìn)程序，最終實(shí)現(xiàn)了Miller-Rabin大素?cái)?shù)判斷算法。
下面是研究的內(nèi)容和過(guò)程：
1.三種大素?cái)?shù)判斷算法
????????我調(diào)研了三種大素?cái)?shù)判斷算法，它們分別是：費(fèi)馬（Fermat）素性檢驗(yàn)、Miller-Rabin素?cái)?shù)測(cè)試算法和AKS素?cái)?shù)測(cè)試。前面兩者屬于隨機(jī)素性檢測(cè)，而AKS屬于確定性素性檢測(cè)。
i.費(fèi)馬（Fermat）素性檢驗(yàn)
????????費(fèi)馬素性檢驗(yàn)是一種素?cái)?shù)判定法則，利用隨機(jī)化算法判斷一個(gè)數(shù)是合數(shù)還是可能是素?cái)?shù)。
費(fèi)馬素性檢驗(yàn)的原理如下：
????????根據(jù)費(fèi)馬小定理：如果p是素?cái)?shù)，1<=a<=p-1，那么有
。如果我們想知道n是否是素?cái)?shù)，我們?cè)谥虚g選取a，看看上面等式是否成立。如果對(duì)于數(shù)值a等式不成立，那么n是合數(shù)。如果有很多的a能夠使等式成立，那么我們可以說(shuō)n可能是素?cái)?shù)，或者偽素?cái)?shù)。
????????在我們檢驗(yàn)過(guò)程中，有可能我們選取的a都能讓等式成立，然而n卻是合數(shù)。這時(shí)等式
? 被稱為Fermat liar。如果我們選取滿足下面等式的a: 
，那么a也就是對(duì)于n的合數(shù)判定的Fermat witness。
????????由于費(fèi)馬小定理的逆定理并不正確，對(duì)于卡邁克爾數(shù)即滿足費(fèi)馬小定理的逆定理但是不為素?cái)?shù)的數(shù)，雖然卡邁克爾數(shù)很少，在1~100000000范圍內(nèi)的整數(shù)中，只有255個(gè)卡邁克爾數(shù)，但是已經(jīng)使他的效果落后于Miller-Rabin和Solovay-Strassen素性檢驗(yàn)。
????????由于屬于隨機(jī)性算法，故費(fèi)馬素性檢驗(yàn)并不是保證完全正確的。在選取底數(shù)a時(shí)，有二分之一的概率出錯(cuò)，但是可以通過(guò)多次選取底數(shù)來(lái)使出錯(cuò)概率降下期望值。
????????在重復(fù)k次成立的情況下，n為合數(shù)的可能性小于1/2k。
ii.AKS素?cái)?shù)測(cè)試
????????AKS素?cái)?shù)測(cè)試是一個(gè)決定型素?cái)?shù)測(cè)試算法 ，由三個(gè)來(lái)自印度坎普爾理工學(xué)院的計(jì)算機(jī)科學(xué)家在2002年8月6日發(fā)表于一篇題為素?cái)?shù)屬于P的論文。這個(gè)算法可以在多項(xiàng)式時(shí)間之內(nèi)，決定一個(gè)給定整數(shù)是素?cái)?shù)或者合數(shù)。
????????AKS 素?cái)?shù)測(cè)試主要是基于以下定理：整數(shù)n(≥ 2)是素?cái)?shù)，當(dāng)且僅當(dāng)
????????這個(gè)同余多項(xiàng)式對(duì)所有與n互素的整數(shù)a均成立。這個(gè)定理是費(fèi)馬小定理的一般化，并且可以簡(jiǎn)單的使用二項(xiàng)式定理跟二項(xiàng)式系數(shù)的這個(gè)特征: 
，對(duì)任何0<k<n，當(dāng)且僅當(dāng)n是素?cái)?shù)來(lái)證明出此定理。
????????為了減少計(jì)算復(fù)雜度，AKS改為使用以下的同余多項(xiàng)式：
????????這個(gè)同余式可以在多項(xiàng)式時(shí)間之內(nèi)檢查完畢。這里我們要注意所有的素?cái)?shù)必定滿足此條件式。然而，有一些合數(shù)也會(huì)滿足這個(gè)條件式。有關(guān)AKS正確性的證明包含了推導(dǎo)出存在一個(gè)夠小的r以及一個(gè)夠小的整數(shù)集合A，令如果此同余式對(duì)所有A里面的整數(shù)都滿足，則n必定為素?cái)?shù)。
iii.Miller-Rabin素?cái)?shù)測(cè)試算法
????????Miller-Rabin素性檢驗(yàn)是一種素?cái)?shù)判定法則，利用隨機(jī)化算法判斷一個(gè)數(shù)是合數(shù)還是可能是素?cái)?shù)?？▋?nèi)基梅隆大學(xué)的計(jì)算機(jī)系教授Gary Lee Miller首先提出了基于廣義黎曼猜想的確定性算法，由于廣義黎曼猜想并沒(méi)有被證明，其后由以色列耶路撒冷希伯來(lái)大學(xué)的Michael O.Rabin教授作出修改，提出了不依賴于該假設(shè)的隨機(jī)化算法。
????????米勒-拉賓檢測(cè)依賴以下定理：
????????如果p是素?cái)?shù)，x是小于p的正整數(shù)，且x^2 = 1 mod p，則x要么為1，要么為p-1。簡(jiǎn)單證明：如果x^2 = 1 mod p，則p整除x^2 – 1，即整除(x+1)(x-1)，由于p是素?cái)?shù)，所以p要么整除x+1，要么整除x-1，前者則x為p-1，后者則x為1。
????????素性檢測(cè)首先利用了因數(shù)分解式，將冪次n-1降低為以2為階的各次冪，再利用中國(guó)剩余定理，推出強(qiáng)偽素?cái)?shù)的滿足條件，在算法優(yōu)化中，采用模平方算法降低復(fù)雜度，這也是該算法的優(yōu)勢(shì)之一，大大提高了效率。
????????具體操作如下所示：
????????在k次檢測(cè)通過(guò)的情況下，n為合數(shù)的概率小于1/4k。相比之下，這樣的出錯(cuò)概率遙遙低于費(fèi)馬素性檢測(cè)。而且需要注意的是，這是個(gè)很保守的估計(jì)，實(shí)際使用的效果要好得多。
2. Miller-Rabin大素?cái)?shù)判斷算法的實(shí)現(xiàn)
????????有了前面的理論基礎(chǔ)，現(xiàn)在我就可以開(kāi)始進(jìn)行編程來(lái)實(shí)現(xiàn)Miller-Rabin大素?cái)?shù)判斷算法了。
i.首先編寫(xiě)一個(gè)python程序來(lái)驗(yàn)證Miller-Rabin大素?cái)?shù)判斷算法
????????我用python編程實(shí)現(xiàn)了Miller-Rabin大素?cái)?shù)判斷算法，由于此時(shí)我無(wú)法找到很大的素?cái)?shù)，所以只對(duì)一些較小的、常見(jiàn)的素?cái)?shù)進(jìn)行判斷，這樣有利于后續(xù)判斷大數(shù)是否為素?cái)?shù)。程序在pycharm中如下所示（完整代碼見(jiàn)附錄1）：
?????????下面是我每次隨機(jī)輸入一個(gè)數(shù)，程序?qū)υ摂?shù)是否為素?cái)?shù)的判斷（prime為素?cái)?shù)，composite為合數(shù)）：
????????可以看到，該Miller-Rabin素?cái)?shù)判斷程序?qū)ι鲜鲚斎氲臄?shù)字進(jìn)行判斷的結(jié)果都是正確的。那么這個(gè)程序是否能夠?qū)艽蟮乃財(cái)?shù)進(jìn)行判斷呢？目前還沒(méi)有確定的答案，因?yàn)槲椰F(xiàn)在不能找到一個(gè)很大的素?cái)?shù)作為程序的輸入來(lái)進(jìn)行判斷，比如找到一個(gè)512bits的大數(shù)。那么，下一步便是編寫(xiě)生成大素?cái)?shù)的程序，我們?cè)谠摮绦蜻\(yùn)行后得到一個(gè)很大的素?cái)?shù)后，再把該素?cái)?shù)放入上面的Miller-Rabin素?cái)?shù)判斷程序中，觀察判斷的結(jié)果，從而能夠確認(rèn)Miller-Rabin素?cái)?shù)判斷程序?qū)艽蟮臄?shù)進(jìn)行素性檢測(cè)是否有效。
ii.使用GMP庫(kù)生成隨機(jī)大素?cái)?shù)
????????通過(guò)調(diào)研發(fā)現(xiàn)，可以直接使用GMP庫(kù)來(lái)生成一個(gè)512bits的大素?cái)?shù)，在DevC++中的程序如下（p為512bits的大素?cái)?shù)，完整代碼見(jiàn)附錄2）：
??????????運(yùn)行該程序后，我得到了一個(gè)512bits的大素?cái)?shù)，其十進(jìn)制表示如下：
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006083527
????????然后我將該大素?cái)?shù)作為輸入，運(yùn)行上面的Miller-Rabin素?cái)?shù)判斷程序，結(jié)果如下：
????????可以看到，該程序?qū)⑤斎肱卸樗財(cái)?shù)，這與事實(shí)是相符的，說(shuō)明上面的Miller-Rabin素?cái)?shù)判斷程序在一定程度上的準(zhǔn)確率是比較可靠的。
????????當(dāng)然，這里使用的是GMP庫(kù)來(lái)生成512bits的大素?cái)?shù)，其實(shí)用python也能得到大素?cái)?shù)，附錄3中給出了使用python生成512bits大素?cái)?shù)的核心函數(shù)。
四、研究結(jié)果及其分析
????????從上面的研究?jī)?nèi)容可以看到，將Miller-Rabin素性檢測(cè)算法用于大素?cái)?shù)的判斷是能夠得到較好的結(jié)果的。Miller-Rabin素性檢測(cè)其實(shí)就是Fermat算法加入二次探測(cè)定理的一種實(shí)現(xiàn)，它的理論基礎(chǔ)是由Fermat定理引申而來(lái)，因此它具備了Fermat檢測(cè)算法的優(yōu)勢(shì)，同時(shí)進(jìn)一步降低了判斷的錯(cuò)誤率。在運(yùn)行python程序?qū)^小的數(shù)進(jìn)行素性檢測(cè)時(shí)，得到結(jié)果的速度很快，這也是Miller-Rabin素性檢測(cè)算法的一個(gè)優(yōu)點(diǎn)。在使用GMP庫(kù)獲取512bits的大素?cái)?shù)時(shí)，耗費(fèi)的時(shí)間會(huì)長(zhǎng)一點(diǎn)，但當(dāng)我把512bits的大數(shù)作為輸入運(yùn)行Miller-Rabin大素?cái)?shù)判斷程序時(shí)，得到結(jié)果的速度依然很快，且結(jié)果是正確的。因此，本次編程實(shí)現(xiàn)Miller-Rabin大數(shù)素性檢測(cè)取得了一定的成功。
????????當(dāng)然，本次研究還有需要改進(jìn)的地方，比如在獲取512bits的大素?cái)?shù)的方法上，除了使用GMP這個(gè)現(xiàn)有的庫(kù)來(lái)實(shí)現(xiàn)，還可以自己編寫(xiě)程序，從更加底層的角度，來(lái)得到大素?cái)?shù)。對(duì)于Miller-Rabin大素?cái)?shù)判斷程序，因?yàn)槲也殚喌馁Y料有限，精力也有限，所以我認(rèn)為一定還可以在此程序基礎(chǔ)上進(jìn)行改進(jìn)，使得判斷的準(zhǔn)確性更高，即錯(cuò)誤率更低。這些都是通過(guò)本次研究結(jié)果看到的不足，后續(xù)我會(huì)持續(xù)進(jìn)行研究和改進(jìn)。
五、結(jié)論
????????在本次研究中，我熟悉了三種常見(jiàn)的大數(shù)素性檢測(cè)的算法，同時(shí)理解了大數(shù)生成的原理，利用GMP庫(kù)生成512bits的大素?cái)?shù)，使用python語(yǔ)言編寫(xiě)了Miller-Rabin大素?cái)?shù)判斷算法的程序，將大素?cái)?shù)作為輸入，運(yùn)行程序，得到了正確的判斷結(jié)果。
????????研究結(jié)果說(shuō)明，Miller-Rabin算法用于大數(shù)素性檢測(cè)的優(yōu)勢(shì)很明顯：速度快，錯(cuò)誤率低；同時(shí)，獲取大素?cái)?shù)的方法不只一種，還可以去探索新的方法，我編寫(xiě)的python程序也有可以改進(jìn)的地方，通過(guò)后續(xù)的研究，我相信能夠把程序的素?cái)?shù)判斷錯(cuò)誤率降得更低。
????????通過(guò)本次研究，我對(duì)素?cái)?shù)在密碼學(xué)中發(fā)揮的重要性有了更深刻的理解，對(duì)
????????Miller-Rabin大素?cái)?shù)判斷算法的原理有了較為熟悉的掌握，在編寫(xiě)程序?qū)崿F(xiàn)該算法的過(guò)程中，我強(qiáng)化了對(duì)其的理解，也提高了自己的動(dòng)手能力，收獲頗豐。
六、參考文獻(xiàn)
[1]? 謝建全.一種實(shí)用的大素?cái)?shù)快速生成方法[J].信息安全與通信保密.2006,(9).56-58.
[2]? 耿海飛,蘇錦海.大素?cái)?shù)的快速生成研究與實(shí)現(xiàn)[J].電腦與信息技術(shù).2005,(2).9-11,32.
[3]? 韋萍萍,戎士奎.判定素?cái)?shù)的新方法及程序[J].貴州教育學(xué)院學(xué)報(bào)(自然科學(xué)).2005,(2).1-3.
[4]? 朱文余.AKS算法及關(guān)于它的一種改進(jìn)算法的實(shí)現(xiàn)分析[J].四川大學(xué)學(xué)報(bào)（自然科學(xué)版）.2005,(3).459-466.
[5] 瞿白.大數(shù)的生成和素性檢驗(yàn)[J].電腦知識(shí)與技術(shù).2010,(6).7353-7356.
七、附錄
1.驗(yàn)證Miller-Rabin大素?cái)?shù)判斷算法的python程序
import random
def isprime(n):
??? k,p=0,n-1
??? while (p&1)==0:
??????? p=p>>1
??????? k+=1
??? for j in range(6):
??????? a=random.randint(1,n-1)
??????? b=pow(a,p,n)
??????? flag=0
??????? if b==1:
??????????? continue文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-490970.html
??????? for i in range(k):
??????????? if (b+1)%n==0:
??????????????? flag=1
??????????????? break
??????????? else:
???????? ???????b=(b*b)%n
??????? if flag==1:
??????????? continue
??????? else:文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-490970.html
??????????? return False
??? return True
n=int(input())
if isprime(n):
??? print(n,'is prime')
else:
??? print(n,'is composite')
if __name__ == '__main__':
isprime(n)
2.使用GMP庫(kù)生成隨機(jī)大素?cái)?shù)的C語(yǔ)言程序（p為512bits的大素?cái)?shù)）
#include <stdio.h>
#include <gmp.h>
#include<time.h>
int main()
{
??? clock_t time = clock();
??? gmp_randstate_t grt;
??? gmp_randinit_default(grt);
??? gmp_randseed_ui(grt, time);
??? mpz_t p;
??? mpz_init(p);
??? mpz_urandomb(p, grt, 512);
??? mpz_nextprime(p, p);
??? gmp_printf("p = %Zd\n\n", p);
??? return 0;
}
3.使用python生成512bits大素?cái)?shù)的核心函數(shù)
i.生成偽素?cái)?shù)
def proBin(w):? # w表示希望產(chǎn)生位數(shù)
??? list = []
??? list.append(1)? #最高位定為1
??? for i in range(w - 2):
??????? c = randint(0, 1)
??????? list.append(c)
??? list.append(1)
??? ls2 = [str(j) for j in list]
??? ls3 = ''.join(ls2)
??? b = int(ls3[0])
??? for i2 in range(len(ls3) - 1):
??????? b = b << 1
??????? b = b + int(ls3[i2 + 1])
??? d = long(b)
return d
ii.產(chǎn)生512位素?cái)?shù)
def pro512():?????????? # 產(chǎn)生512位素?cái)?shù)
??? while 1:
??????? d = proBin(512)
??????? for i in range(50):? # 偽素?cái)?shù)附近50個(gè)奇數(shù)都沒(méi)有真素?cái)?shù)的話，重新再產(chǎn)生一個(gè)偽素?cái)?shù)
??????????? u = testMillerRabin(d+2*(i), 5)
??????????? if u:
??????????????? b = d + 2*(i)
??????????????? break
??????????? else:
??????????????? continue
??????? if u:
??????????? return b
??????? else:
??????????? continue
到了這里，關(guān)于Miller-Rabin大素?cái)?shù)判斷算法的原理及其實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
