米勒-拉賓檢驗

米勒-拉賓質數判定法是一種質數判定法則，利用隨機化演算法判斷一個數是合數還是"可能是"素數。1976年，卡內基梅隆大學的計算機系教授首先提出了基於廣義黎曼猜想的確定性演算法，由於廣義黎曼猜想並沒有被證明，於1980年，由以色列耶路撒冷希伯來大學的-{zh-cn:邁克爾·拉賓; zh-tw:麥可·拉賓}-教授作出修改，提出了不依賴於該假設的隨機化演算法。概念.首先介紹一個相關的引理。我們發現 formula_1 和 formula_2 總是得到 formula_3，我們稱 formula_4 和 formula_3 是 formula_6 的“平凡平方根”，當 formula_7 是素數且 formula_8 時，不存在 formula_6 的“非平凡平方根”。為了證明該引理，首先假設 formula_10 是 formula_6 的平方根之一，於是有formula_12formula_13也就是說，素數 formula_7 能夠整除 formula_15 或者 formula_16，根據歐幾里得引理，formula_17 或者 formula_18 能夠被 formula_7 整除，即 formula_20 或 formula_21,即 formula_10 是 formula_6 的平凡平方根。現在假設 formula_24 是一個素數，且 formula_25。於是 formula_26 是一個偶數，可以被表示為 formula_27 的形式，formula_28 和 formula_29 都是正整數且formula_29是奇數。對任意在 formula_31 範圍內的 formula_32，必須滿足以下兩種形式的一種：formula_33formula_34其中 formula_35 是某個滿足 formula_36 的整數。因為由於 費馬小定理 ，對於一個素數 formula_24 ，有formula_38又由於上面的引理，如果我們不斷對formula_39取平方根後，我們總會得到 formula_3 和 formula_4。如果我們得到了 formula_4 ，意味著②式成立，formula_24 是一個素數。如果我們從未得到 formula_4 ，那麼透過這個過程我們已經取遍了所有 formula_45 的冪次，即①式成立。米勒-拉賓素性測試就是基於上述原理的逆否，也就是說，如果我們能找到這樣一個 formula_32，使得對任意formula_36以下兩個式子均滿足：formula_48formula_49那麼 formula_24 就不是一個素數。這樣的 formula_32 稱為 formula_24 是合數的一個憑證，即當formula_24確實是一個合數，但是對當前選取的 formula_32 來說上述兩個式子均不滿足，這時我們認為formula_24是基於formula_32的大機率素數。每個奇合數 formula_24 都有很多個對應的憑證 formula_32，但是要生成這些 formula_32 並不容易。當前解決的辦法是使用機率性的測試。我們從集合 formula_31 中隨機選擇非零數 formula_32，然後檢測當前的 formula_32 是否是 formula_24 為合數的一個憑證。如果 formula_24 本身確實是一個合數，那麼大部分被選擇的 formula_32 都應該是 formula_24 的憑證，也即透過這個測試能檢測出 formula_24 是合數的可能性很大。然而，仍有極小機率的情況下我們找到的 formula_32 是一個“強偽證”。透過多次獨立測試不同的 formula_32，我們能減少這種出錯的機率。對於測試一個大數是否是素數，常見的做法隨機選取基數formula_32，畢竟我們並不知道憑證和偽證在formula_74這個區間如何分佈。典型的例子是 Arnault 曾經給出了一個397位的合數formula_24，但是所有小於307的基數formula_32都是formula_24是素數的“強偽證”。不出所料，這個大合數通過了 Maple 程式的codice_1 函式。這個函式透過檢測 formula_78 這幾種情況來進行素性檢驗。例子.假設我們需要檢驗 formula_79 是否是一個素數。首先formula_80，於是我們得到了formula_81和formula_82.我們隨機從formula_83中選取formula_32，假設formula_85，於是有：formula_86formula_87因為我們得到了一個 -1，所以要麼formula_79確實是一個素數，要麼formula_85是一個“強偽證”。我們再選取formula_90，於是有：formula_91formula_92即formula_90是formula_79為合數的一個憑證，而formula_85是一個“強偽證”。選取特定的整數可以在一定範圍內確定某個整數是質數還是合數。對於小於formula_96的情形，選取formula_97共三個憑據可以做到這一點；對於小於formula_98的情形，選取formula_99共七個憑據可以做到這一點。演算法複雜度.這一演算法可以被表示成如下虛擬碼：Input #1: "n" &gt; 3, an odd integer to be tested for primality;Input #2: "k", a parameter that determines the accuracy of the testOutput: "composite" if "n" is composite, otherwise "probably prime"write "n" − 1 as 2"r"·"d" with "d" odd by factoring powers of 2 from "n" − 1WitnessLoop: repeat "k" times:pick a random integer "a" in the range [2, "n" − 2]"x" ← "a""d" mod "n"if "x" = 1 or "x" = "n" − 1 thencontinue WitnessLooprepeat "r" − 1 times:"x" ← "x"2 mod "n"if "x" = "n" − 1 thencontinue WitnessLoopreturn "composite"return "probably prime"使用，這個演算法的時間複雜度是formula_100，formula_101是我們測試的不同的 formula_32 的值。也就是說，這是一個高效的多項式時間演算法。使用快速傅立葉變換能夠將這個時間推進到 O("k" log2"n" log log "n" log log log "n") = Õ("k" log2"n").如果我們加入最大公因數演算法到上述演算法中，我們有時候可以得到 formula_24 的因數，而不僅僅是證明 formula_24 是一個合數。例如，若 formula_24 是一個基於formula_32 的可能的素數，但不是一個大機率素數，則formula_107或formula_108將得到 formula_24 的因數。如果因式分解是必要的，這一formula_110演算法可以加入到上述的演算法中，代價是增加了一些額外的運算時間。例如，假設 formula_111，則formula_112.於是formula_113，這也告訴我們 formula_24 不是一個大機率素數，即 formula_24 是一個合數。如果這個時候我們求最大公因數，我們可以得到一個formula_111的因數：formula_117.這時可行的，因為formula_111是一個基於2的偽素數，但不是一個“強偽素數”。示例程式碼.下面是根據以上定義而使用Magma語言編寫的“米勒-拉賓”檢驗程式。function ModPotenz(a,b,n)erg:=1;while (b ne 0) dob, rest:=Quotrem(b,2);if (rest ne 0) then erg:=((erg*a) mod n); end if;a:= (a^2 mod n);end while;return erg;end function;function Miller_rabin(n)if (n mod 2 ne 0) thend:=n-1; s:=0;t:=50;while (d mod 2) eq 0 dod:=d div 2;s:=s+1;end while;k:=0;while(k lt t) doa:=Random(1,n-1);k:=k+1;if GCD(a,n) ne 1 thencontinue;end if;x:=ModPotenz(a,d,n);if(x ne 1) thenfor r in [0,s-1] dox:=ModPotenz(a,2^r*d,n);if(x eq (n-1)) thenreturn "probably prime";end if;end for;elif (x eq 1) thenbreak;end if;end while;end if;return "composite";end function;