首先介紹一個相關的引理。我們發現
1
2
mod
p
{\displaystyle 1^{2}{\bmod {p}}}
和
(
−
1
)
2
mod
p
{\displaystyle (-1)^{2}{\bmod {p}}}
總是得到
1
{\displaystyle 1}
,我們稱
−
1
{\displaystyle -1}
和
1
{\displaystyle 1}
是
1
mod
p
{\displaystyle 1{\bmod {p}}}
的「平凡平方根」,當
p
{\displaystyle p}
是質數且
p
>
2
{\displaystyle p>2}
時,不存在
1
mod
p
{\displaystyle 1{\bmod {p}}}
的「非平凡平方根」。為了證明該引理,首先假設
x
{\displaystyle x}
是
1
mod
p
{\displaystyle 1{\bmod {p}}}
的平方根之一,於是有
x
2
≡
1
(
mod
p
)
{\displaystyle x^{2}\equiv 1{\pmod {p}}}
(
x
+
1
)
(
x
−
1
)
≡
0
(
mod
p
)
{\displaystyle (x+1)(x-1)\equiv 0{\pmod {p}}}
也就是說,質數
p
{\displaystyle p}
能夠整除
(
x
−
1
)
(
x
+
1
)
{\displaystyle (x-1)(x+1)}
或者
x
=
p
−
1
{\displaystyle x=p-1}
,根據歐幾里得引理,
x
−
1
{\displaystyle x-1}
或者
x
+
1
{\displaystyle x+1}
能夠被
p
{\displaystyle p}
整除,即
x
≡
1
(
mod
p
)
{\displaystyle x\equiv 1{\pmod {p}}}
或
x
≡
−
1
(
mod
p
)
{\displaystyle x\equiv -1{\pmod {p}}}
,
即
x
{\displaystyle x}
是
1
mod
p
{\displaystyle 1{\bmod {p}}}
的平凡平方根。
現在假設
n
{\displaystyle n}
是一個質數,且
n
>
2
{\displaystyle n>2}
。於是
n
−
1
{\displaystyle n-1}
是一個偶數,可以被表示為
2
s
∗
d
{\displaystyle 2^{s}*d}
的形式,
s
{\displaystyle s}
和
d
{\displaystyle d}
都是正整數且
d
{\displaystyle d}
是奇數。對任意在
(
Z
/
n
Z
)
∗
{\displaystyle (Z/nZ)^{*}}
範圍內的
a
{\displaystyle a}
,必須滿足以下兩種形式的一種:
a
d
≡
1
(
mod
n
)
①
{\displaystyle a^{d}\equiv 1{\pmod {n}}{\text{ ① }}}
a
2
r
d
≡
−
1
(
mod
n
)
②
{\displaystyle a^{2^{r}d}\equiv -1{\pmod {n}}{\text{ ② }}}
其中
r
{\displaystyle r}
是某個滿足
0
≤
r
≤
s
−
1
{\displaystyle 0\leq r\leq s-1}
的整數。
因為由於 費馬小定理 ,對於一個質數
n
{\displaystyle n}
,有
a
n
−
1
≡
1
(
mod
n
)
{\displaystyle a^{n-1}\equiv 1{\pmod {n}}}
又由於上面的引理,如果我們不斷對
a
n
−
1
{\displaystyle a^{n-1}}
取平方根後,我們總會得到
1
{\displaystyle 1}
和
−
1
{\displaystyle -1}
。如果我們得到了
−
1
{\displaystyle -1}
,意味着②式成立,
n
{\displaystyle n}
是一個質數。如果我們從未得到
−
1
{\displaystyle -1}
,那麼通過這個過程我們已經取遍了所有
2
{\displaystyle 2}
的冪次,即①式成立。
米勒-拉賓質數測試就是基於上述原理的逆否,也就是說,如果我們能找到這樣一個
a
{\displaystyle a}
,使得對任意
0
≤
r
≤
s
−
1
{\displaystyle 0\leq r\leq s-1}
以下兩個式子均滿足:
a
d
≢
1
(
mod
n
)
{\displaystyle a^{d}\not \equiv 1{\pmod {n}}}
a
2
r
d
≢
−
1
(
mod
n
)
{\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}
那麼
n
{\displaystyle n}
就不是一個質數。這樣的
a
{\displaystyle a}
稱為
n
{\displaystyle n}
是合數的一個憑證(witness)。否則
a
{\displaystyle a}
可能是一個證明
n
{\displaystyle n}
是質數的「強偽證」(strong liar),即當
n
{\displaystyle n}
確實是一個合數,但是對當前選取的
a
{\displaystyle a}
來說上述兩個式子均不滿足,這時我們認為
n
{\displaystyle n}
是基於
a
{\displaystyle a}
的大概率質數。
每個奇合數
n
{\displaystyle n}
都有很多個對應的憑證
a
{\displaystyle a}
,但是要生成這些
a
{\displaystyle a}
並不容易。當前解決的辦法是使用概率性的測試。我們從集合
(
Z
/
n
Z
)
∗
{\displaystyle (Z/nZ)^{*}}
中隨機選擇非零數
a
{\displaystyle a}
,然後檢測當前的
a
{\displaystyle a}
是否是
n
{\displaystyle n}
為合數的一個憑證。如果
n
{\displaystyle n}
本身確實是一個合數,那麼大部分被選擇的
a
{\displaystyle a}
都應該是
n
{\displaystyle n}
的憑證,也即通過這個測試能檢測出
n
{\displaystyle n}
是合數的可能性很大。然而,仍有極小概率的情況下我們找到的
a
{\displaystyle a}
是一個「強偽證」(反而表明了
n
{\displaystyle n}
可能是一個質數)。通過多次獨立測試不同的
a
{\displaystyle a}
,我們能減少這種出錯的概率。
對於測試一個大數是否是質數,常見的做法隨機選取基數
a
{\displaystyle a}
,畢竟我們並不知道憑證和偽證在
[
1
,
n
−
1
]
{\displaystyle [1,n-1]}
這個區間如何分佈。典型的例子是 Arnault 曾經給出了一個397位的合數
n
{\displaystyle n}
,但是所有小於307的基數
a
{\displaystyle a}
都是
n
{\displaystyle n}
是質數的「強偽證」。不出所料,這個大合數通過了 Maple 程序的isprime()
函數(被判定為質數)。這個函數通過檢測
a
=
2
,
3
,
5
,
7
,
11
{\displaystyle a=2,3,5,7,11}
這幾種情況來進行質性檢驗。
假設我們需要檢驗
n
=
221
{\displaystyle n=221}
是否是一個質數。首先
n
−
1
=
220
=
(
2
2
)
∗
55
{\displaystyle n-1=220=(2^{2})*55}
,於是我們得到了
s
=
2
{\displaystyle s=2}
和
d
=
55
{\displaystyle d=55}
.我們隨機從
[
1
,
n
−
1
]
{\displaystyle [1,n-1]}
中選取
a
{\displaystyle a}
,假設
a
=
174
{\displaystyle a=174}
,於是有:
a
2
0
d
mod
n
=
174
55
mod
2
21
=
47
≠
1
,
−
1
{\displaystyle a^{2^{0}d}{\bmod {n}}=174^{55}{\bmod {2}}21=47\not =1,-1}
a
2
1
d
mod
n
=
174
110
mod
2
21
=
220
=
−
1
{\displaystyle a^{2^{1}d}{\bmod {n}}=174^{110}{\bmod {2}}21=220=-1}
因為我們得到了一個 -1,所以要麼
n
=
221
{\displaystyle n=221}
確實是一個質數,要麼
a
=
174
{\displaystyle a=174}
是一個「強偽證」。我們再選取
a
=
137
{\displaystyle a=137}
,於是有:
a
2
0
d
mod
n
=
137
55
mod
2
21
=
188
≠
1
,
−
1
{\displaystyle a^{2^{0}d}{\bmod {n}}=137^{55}{\bmod {2}}21=188\not =1,-1}
a
2
1
d
mod
n
=
137
110
mod
2
21
=
205
≠
−
1
{\displaystyle a^{2^{1}d}{\bmod {n}}=137^{110}{\bmod {2}}21=205\not =-1}
即
a
=
137
{\displaystyle a=137}
是
n
=
221
{\displaystyle n=221}
為合數的一個憑證,而
a
=
174
{\displaystyle a=174}
是一個「強偽證」。
選取特定的整數可以在一定範圍內確定(而非單純基於概率猜測)某個整數是質數還是合數。對於小於
2
32
{\displaystyle 2^{32}}
的情形,選取
2
,
7
,
61
{\displaystyle 2,7,61}
共三個憑據可以做到這一點;對於小於
2
64
{\displaystyle 2^{64}}
的情形,選取
2
,
325
,
9375
,
28178
,
450775
,
9780504
,
1795265022
{\displaystyle 2,325,9375,28178,450775,9780504,1795265022}
共七個憑據可以做到這一點[ 1] 。
這一算法可以被表示成如下偽代碼 :
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 ← a d mod n
if x = 1 or x = n − 1 then
continue WitnessLoop
repeat r − 1 times:
x ← x 2 mod n
if x = n − 1 then
continue WitnessLoop
return composite
return probably prime
使用模冪運算 ,這個算法的時間複雜度是
O
(
k
log
3
n
)
{\displaystyle O(k\log ^{3}n)}
,
k
{\displaystyle k}
是我們測試的不同的
a
{\displaystyle a}
的值。也就是說,這是一個高效的多項式時間算法。使用快速傅立葉轉換 能夠將這個時間推進到 O(k log2 n log log n log log log n ) = Õ(k log2 n ).
如果我們加入最大公因數 算法到上述算法中,我們有時候可以得到
n
{\displaystyle n}
的因數,而不僅僅是證明
n
{\displaystyle n}
是一個合數。例如,若
n
{\displaystyle n}
是一個基於
a
{\displaystyle a}
的可能的質數,但不是一個大概率質數,則
gcd
(
(
a
d
mod
n
)
−
1
,
n
)
{\displaystyle \gcd((a^{d}{\bmod {n}})-1,n)}
或
gcd
(
(
a
2
r
d
mod
n
)
−
1
,
n
)
{\displaystyle \gcd((a^{2^{r}d}{\bmod {n}})-1,n)}
將得到
n
{\displaystyle n}
的因數。如果因式分解是必要的,這一
G
C
D
s
{\displaystyle GCDs}
算法可以加入到上述的算法中,代價是增加了一些額外的運算時間。
例如,假設
n
=
341
{\displaystyle n=341}
,則
n
−
1
=
340
=
85
∗
4
{\displaystyle n-1=340=85*4}
.於是
2
85
mod
3
41
=
32
{\displaystyle 2^{85}{\bmod {3}}41=32}
,這也告訴我們
n
{\displaystyle n}
不是一個大概率質數,即
n
{\displaystyle n}
是一個合數。如果這個時候我們求最大公因數,我們可以得到一個
n
=
341
{\displaystyle n=341}
的因數:
gcd
(
(
2
85
mod
3
41
)
−
1
,
341
)
=
31
{\displaystyle \gcd((2^{85}{\bmod {3}}41)-1,341)=31}
.這時可行的,因為
n
=
341
{\displaystyle n=341}
是一個基於2的偽質數,但不是一個「強偽質數」。
下面是根據以上定義而使用Magma語言編寫的「米勒-拉賓」檢驗程序。
function ModPotenz ( a,b,n)
erg := 1 ;
while ( b ne 0 ) do
b , 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 ) then
d := n - 1 ; s := 0 ; t := 50 ;
while ( d mod 2 ) eq 0 do
d := d div 2 ;
s := s + 1 ;
end while ;
k := 0 ;
while ( k lt t ) do
a := Random ( 1 , n - 1 );
k := k + 1 ;
if GCD ( a , n ) ne 1 then
continue ;
end if ;
x := ModPotenz ( a , d , n );
if ( x ne 1 ) then
for r in [ 0 , s - 1 ] do
x := ModPotenz ( a , 2 ^r * d , n );
if ( x eq ( n - 1 )) then
return "probably prime" ;
end if ;
end for ;
elif ( x eq 1 ) then
break ;
end if ;
end while ;
end if ;
return "composite" ;
end function ;