Cryptography Reference
In-Depth Information
to the Fermat and Solovay-Strassen tests, the Miller-Rabin test can prove the
compositeness of a large number
n
with certainty, but it can prove the primality
of
n
only with a certain probability.
The underlying idea of the Miller-Rabin test is that if
n
is a prime, then 1
should have only 2 square roots in
1. Alternatively speaking, if
n
is
nonprime, then there are at least 2 elements
x
of
Z
n
, namely
±
Z
n
with
x
2
≡
1(mod
n
) but
x
1. That is, there will be more square roots of 1 than there should be. The
Miller-Rabin test itself is based on the properties of strong pseudoprimes. If we
want to test the primality of a large odd number
n
=2
r
s
+1, then we randomly
choose an integer
a
between 1 and
n
=
±
−
1.If
a
s
≡
1(mod
n
)
or
a
2
j
s
≡−
1(mod
n
)
for some 0
1,then
n
passes the test for this value of
a
(i.e.,
a
is not
a witness for the compositeness of
n
). Unfortunately, a number that passes the test
is not necessarily prime. In fact, it can be shown that a composite number passes
the test for at most 1
/
4 of the possible values for
a
. Consequently, if
k
tests are
performed on a composite number
n
, then the probability that it passes each test is
at most 1
/
4
k
. This means that the error probability can be made arbitrarily small.
Note that the operation of the Miller-Rabin test is quite simple, though—
even simpler than that of the Solovay-Strassen test. Consequently, the Miller-Rabin
test is the primality (or compositeness) testing algorithm of choice for all practical
purposes.
≤
j
≤
r
−
3.2.5
Factorization
First of all, it can be shown that a prime
p
that divides the product
ab
of two natural
numbers
a
and
b
divides at least one of the two factors (i.e.,
a
or
b
). To prove this
fact, we assume that
p
divides
ab
but not
a
and show that
p
must then divide
b
.
Because
p
is a prime, we have
gcd
(
a, p
)=1and hence there exist
x, y
N
with
gcd
(
a, p
)=1=
ax
+
py
[refer to (3.1)]. This equation can be multiplied with
b
to
get
b
=
abx
+
pby
. Obviously,
p
divides
abx
and
pby
(the right side of the equation),
so
p
must also divide
b
(the left side of the equation).
This result can be generalized to more than two factors. In fact, if
p
divides a
product
∈
