首先介绍一个相关的引理。我们发现 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 ;
參考資料
编辑