米勒-拉宾检验

概念

${\displaystyle x^{2}\equiv 1{\pmod {p}}}$

${\displaystyle (x+1)(x-1)\equiv 0{\pmod {p}}}$

${\displaystyle x}$${\displaystyle 1{\bmod {p}}}$ 的平凡平方根。

${\displaystyle a^{d}\equiv 1{\pmod {n}}{\text{ ① }}}$
${\displaystyle a^{2^{r}d}\equiv -1{\pmod {n}}{\text{ ② }}}$

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

${\displaystyle a^{d}\not \equiv 1{\pmod {n}}}$
${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$

例子

${\displaystyle a^{2^{0}d}{\bmod {n}}=174^{55}{\bmod {2}}21=47\not =1,-1}$
${\displaystyle a^{2^{1}d}{\bmod {n}}=174^{110}{\bmod {2}}21=220=-1}$

${\displaystyle a^{2^{0}d}{\bmod {n}}=137^{55}{\bmod {2}}21=188\not =1,-1}$
${\displaystyle a^{2^{1}d}{\bmod {n}}=137^{110}{\bmod {2}}21=205\not =-1}$
${\displaystyle a=137}$${\displaystyle n=221}$为合数的一个凭证，而${\displaystyle 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]
if x = 1 or x = n − 1 then
continue WitnessLoop
repeat r − 1 times:
x ← x2 mod n
if x = n − 1 then
continue WitnessLoop
return composite
return probably prime


示例代码

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;