Cryptography Reference
In-Depth Information
The important facts about the Miller-Rabin test are captured in the following
theorem:
3
Theorem 6.9
.Ifnis
an odd prime the test always outputs “prime”. If n is an odd composite then the test
outputs “prime” with probability at most
4
−
k
.
The Miller-Rabin test runs in polynomial time O
(
k
len
(
n
)
)
Proof
The running time follows from the fact that the strong probable prime test
runs in time
O
3
.If
n
is prime then the algorithm returns “prime” because
of Theorem 6.6. If
n
is composite then the probability that the algorithm fails to
find a witness at each iteration is
(
len
(
n
)
)
4 by Theorem 6.7, so that the probability that
no witness has been found after
k
iterations (in which case the algorithm returns
“prime”) is
<
1
/
k
.
<(
1
/
4
)
Remark 6.6
The Miller-Rabin test can be viewed as a search for a proof of the
compositeness of
n
in the form of a witness: if
n
is prime then no such proof will be
found and if
n
is composite then the proof will be found with probability
4
−
k
.
Thus the algorithm can prove that an integer is composite but it cannot prove that it
is prime (since usually
k
will be much smaller than
>
1
−
4). Because of this, the
algorithm is often called the
Miller-Rabin compositeness test
. Actually, this test is a
no-biased Monte Carlo algorithm for testing compositeness and a yes-biased Monte
Carlo algorithm for testing primality. Thus it shows that the decision problemwhether
an integer
n
is composite is in the class
(
n
−
1
)/
RP
and the decision problem whether
n
is
primeisinco
(both these facts are superseded by the AKS test mentioned below,
which shows that both problems are actually in
RP
P
).
The next function implements theMiller-Rabin test inMaple, using the previously
defined function
StrongProbablePrimeTest
. The input consists of the odd
integer
n
to be tested and a positive integer
k
to set the number of random bases to be
used. In practice, we will use Maple's default pseudo-random algorithm to generate
these bases, so that they will not be really random but this is not a big concern here
since unpredictability is not required. The output is
true
if
n
is either prime or a
strong pseudoprime for the
k
bases considered (in which case
n
will be declared a
probable prime) and
false
otherwise (so that
true
corresponds to “prime” and
false
corresponds to “composite” in the sense of Algorithm 6.2):
> MillerRabin := proc(n::And(posint, odd), k::posint)
local t, i;
i:=1;
t := true;
if4<nthen
while t and i <= k do
t := StrongProbablePrimeTest[rand(2..n-2)()](n);
i:=i+1
end do
else
t := evalb(n = 3)
end if;
t
end proc:
