Cryptography Reference
In-Depth Information
the following theorem which, assuming the verification of the Extended Riemann
Hypothesis, shows that the first witness does indeed have a polynomial growth:
Theorem 6.8
(Bach)
If the Extended Riemann Hypothesis is true and n
>
1
is an
ln
2
n.
odd composite integer, then there is a witness b for n such that b
<
From this it follows that, if we assume that the ERH holds, in order to test
n
for
primality it suffices to perform the strong compositeness test on
n
for all bases up
to ln
2
n
. Thus we obtain a polynomial-time primality test, conditional on the ERH,
with running time
O
ln
5
n
. This test is often called
Miller's deterministic test
.
Miller's test, however, is not very satisfactory for a couple of reasons. The first is
that the ERH remains unproven and the second that this test is inefficient in practice.
For example, note that testing the primality of a 2048-bit number would require
performing about 2 million strong probable prime tests. This number can be reduced
since many of these tests are not independent—for example, the bases which are
powers of integers should be disregarded and also, if
n
is a strong pseudoprime to the
bases
a
and
b
, then it is very likely also a pseudoprime to the base
ab
[27]. But even
considering only prime bases less than ln
2
n
, about 150000 strong probable prime
tests would have to be performed in this case.
The fact that this test is not practical is not a big problem anyway. On the one
hand, from the theoretical point of view this does not matter because, as we will
indicate below, it is now known that the primality of an integer can be checked
unconditionally in polynomial time (or, as in the title of the original paper where
this is proved: PRIMES is in P). From a more practical point of view, the important
thing is that we can turn the previous test into a very efficient one by trading off the
theoretical assurance that the test always gives the correct answer and replacing it
by a very high probability that this is indeed the case.
The idea to obtain a very efficient test starting with the strong probable prime test
is just to choose
k
random bases (where
k
(
)
0) and submit the integer
n
to the strong
probable prime test for each of these bases; if for any of these bases
n
fails the strong
probable prime test,
n
is declared composite and if, on the contrary,
n
passes all
k
tests,
n
is declared prime. This is the
Miller-Rabin test
:
>
Algorithm 6.2. Miller-Rabin test.
Input
: An odd integer
n
>
3 and a parameter
k
>
0.
Output
: Either “prime” or “composite”.
1.
for
i
from
1
to
k
do
b
←[
2
,
n
−
2
]
;
if
n
fails the strong probable prime test to base
b
then
return
“composite”
end if
end do
;
2.
return
“prime”.
