米勒-拉賓素性檢驗

首先介紹一個相關的引理。

和

總是得到1，稱這兩個數為1的“平凡平方根”。當p是素數且p>2時，不存在

的“非平凡平方根”。為了證明該引理，我們假設x是

的平方根，於是有 ^[1] 

推出p|(x+1)(x-1)，也就是説，p|x+1或p|x-1。

假設n是一個奇素數，且 n>2。於是n-1是一個偶數，可以被表示為

的形式，s和d都是正整數且d是奇數。對任意在

範圍內的a 和

，必滿足以下兩種形式的一種：

因為由於費馬小定理，對於一個素數n，有

又由於上面的引理，如果我們不斷對

取平方根，我們總會得到 1 或 -1。如果我們得到了 -1，意味着②式成立，n是一個素數。如果我們從未得到 -1，那麼通過這個過程我們已經取遍了所有2的冪次，即①式成立。

米勒-拉賓素性測試就是基於上述原理的逆否，也就是説，如果如果我們能找到這樣一個a，使得對任意

以下兩個式子均滿足：

那麼n就不是一個素數。這樣的a稱為n是合數的一個憑證（witness）。否則a可能是是一個證明n是素數的“強偽證”（strong liar），即當n確實是一個合數，但是對當前選取的a來説上述兩個式子均不滿足，這時我們認為n是基於a的大概率素數。

每個奇合數n都有很多個對應的憑證a，但是要生成這些a並不容易。當前解決的辦法是使用概率性的測試。我們從集合

中隨機選擇非零數a，然後檢測當前的a是否是n為合數的一個憑證。如果n本身確實是一個合數，那麼大部分被選擇的a都應該是n的憑證，也即通過這個測試能檢測出n是合數的可能性很大。然而，仍有極小概率的情況下我們找到的a是一個“強偽證”（反而表明了n可能是一個素數）。通過多次獨立測試不同的a，我們能減少這種出錯的概率。

對於測試一個大數是否是素數，常見的做法隨機選取基數a，畢竟我們並不知道憑證和偽證在 [1,n-1]這個區間如何分佈。典型的例子是 Arnault 曾經給出了一個397位的合數n，但是所有小於307的基數a都是n是素數的“強偽證”。不出所料，這個大合數通過了 Maple 程序的isprime()函數（被判定為素數）。這個函數通過檢測 a=2,3,5,7,11這幾種情況來進行素性檢驗。

假設我們需要檢驗n=221是否是一個素數。首先

，於是我們得到了 s=2和d=55。我們隨機從[1,n-1]中選取a，假設a=174，於是有：

因為我們得到了一個 -1，所以要麼n=221確實是一個素數，要麼a=174是一個“強偽證”。我們再選取a=137，於是有：

即a=137是n=221為合數的一個憑證，而a=174是一個“強偽證”。

這一算法可以被表示成如下偽代碼：

Input #1: n > 3, an odd integer to be tested for primality;

Input #2: k, a parameter that determines the accuracy of the test

Output: composite if n is composite, otherwise probably prime

write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1

WitnessLoop: repeat k times:

pick a random integer a in the range [2, n − 2]

x ← ad mod n

if x = 1 or x = n − 1

then

continue WitnessLoop

repeat r − 1 times:

x ← x2 mod n

if x = 1

then

return composite

if x = n − 1

then

continue WitnessLoop

return compositereturn probably prime

使用模冪運算，這個算法的時間複雜度是

，k是我們測試的不同的a的值。也就是説，這是一個高效的多項式時間算法。使用快速傅里葉變換能夠將這個時間推進到O(klognlog lognlog log logn) =Õ(klogn).

如果我們加入最大公因數算法到上述算法中，我們有時候可以得到n的因數，而不僅僅是證明n是一個合數。例如，若n是一個基於a的可能的素數，但不是一個大概率素數，則

或

將得到n的因數。如果因式分解是必要的，這一GCDs算法可以加入到上述的算法中，代價是增加了一些額外的運算時間。

例如，假設n=341，則n-1=340=85*4。於是

，這也告訴我們n不是一個大概率素數，即n是一個合數。如果這個時候我們求最大公因數，我們可以得到一個n=341的因數：

。這是時可行的，因為n=341是一個基於2的偽素數，但不是一個“強偽素數”。