Cryptography Reference
In-Depth Information
would like to introduce a few considerations that will improve our understanding
of the most widely used probabilistic primality tests
Let us make the hypothesis that
n
is prime. Then by Fermat's little theorem
we have
a
n
−
1
≡
1mod
n
for integers
a
that are not multiples of
n
. The square
root of
a
n
−
1
mod
n
can assume only the value
1
or
−
1
, since these are the
only solutions of the congruence
x
2
≡
1mod
n
(see Section 10.4.1). If we also
compute from
a
n
−
1
mod
n
the successive square roots
a
(
n
−
1)
/
2
mod
n,
a
(
n
−
1)
/
2
t
a
(
n
−
1)
/
4
mod
n,
mod
n,
one after another until
(
n −
1)
/
2
t
is odd, and if in the process we arrive at a
residue not equal to 1, then this residue must have the value
...,
1
, for otherwise,
n
cannot be prime, which we have hypothesized. For the case that the first square
root different from
1
has the value
−
1
, we stick by our hypothesis that
n
is prime.
If
n
is nevertheless composite, then we shall call
n
on the basis of this special
property a
strong pseudoprime to the base
a
. Strong pseudoprimes to a base
a
are
always Euler pseudoprimes to the base
a
(see [Kobl], Chapter 5).
We assemble all of this into the following probabilistic primality test, though
for the sake of efficiency we shall first compute the power
b
=
a
(
n
−
1)
/
2
t
mod
n
with odd
(
n −
1)
/
2
t
, and if this is not equal to
1
, we continue to square
b
until we
obtain a value of
−
1
or have reached
a
(
n
−
1)
/
2
mod
n
. In the last case we must
have either
b
=
−
1
or that
n
is composite. The idea of shortening the algorithm
so that the last square does not have to be calculated has been taken from [Cohe],
Section 8.2.
±
Probabilistic primality test à la Miller-Rabin for odd integers
n>
1
1.
Determine
q
and
t
with
n −
1=2
t
q
,with
q
odd.
a
q
mod
n
.If
b
=1
,
output “
n
is probably prime” and terminate the algorithm.
2.
Choose a random integer
a
,
1
<a<n
.Set
e
←
0
,
b
←
b
2
mod
n
and
e ← e
+1
.Ifnow
b
=
n −
1
, then output “
n
is composite.” Otherwise,
output “
n
is probably prime.”
3.
As long as we have
b
≡±
1mod
n
and
e<t
−
1
, set
b
←
With a running time of
O
log
3
n
for the exponentiations, the Miller-Rabin
test (MR test for short) has complexity the same order of magnitude as the
Solovay-Strassen test.
The existence of strong pseudoprimes means that the Miller-Rabin primality
test offers us certainty only about the compositeness of numbers. The number
91
, which we trotted out above as an example of an Euler pseudoprime (to base
9) is also—again to base 9—a strong pseudoprime. Further examples of strong
pseudoprimes are
2152302898747 = 6763
·
10627
·
29947
