Cryptography Reference
In-Depth Information
have to prove that
b
is a quadratic residue if and only if
b
n
−
1
≡
1 (mod
n
). We already
2
did it for Theorem 6.6.
The converse is a little more technical.
We assume that the test holds for more than half of the
b
is in
Z
n
. We notice that
the set of all
b
for which the test holds is actually a subgroup of
Z
n
. (The test predicate
is stable by multiplication.) Therefore the probability that the test holds for a random
b
is one over the index of the subgroup. If the probability is greater than
1
2
, this means
that the subgroup is
Z
n
itself. Therefore the test must hold for all
b
.
By squaring the test predicate, we notice that this implies
b
n
−
1
≡
1 (mod
n
) for all
Z
n
. Thus
n
is either prime or a Carmichael number. All we have to do is show that
the test predicate cannot hold with Carmichael numbers.
b
∈
We already know that a Carmichael number is a product of pairwise different
prime numbers. Let
n
p
r
be the factorization of
n
into primes. Seeing
Z
n
=
p
1
···
p
i
as independent bits indicating
like
Z
p
1
×···×
Z
p
r
, we can consider all the
b
i
=
1). Obviously,
n
is the
product of all these independent bits
. D
ue to Theorem 7.1, we know
tha
t
p
i
−
whether
b
is (as a
Z
p
i
element) a quadratic residue (
+
1) or not (
−
1 divides
, then
b
n
−
1
1 (mod
p
i
). Otherwise,
b
n
−
1
n
−
1
2
n
−
1. If
p
i
−
1 divides
≡
≡
b
i
(mod
p
i
).
2
2
1 such that
b
n
−
1
We define
b
i
=±
b
i
(mod
p
i
). We know that depending on
i
only,
≡
2
b
i
is equal to
b
i
or to 1. Hence
b
i
can be written
f
i
(
b
i
). Thus for all
i
we have
r
f
i
(
b
i
)
≡
b
j
(mod
p
i
)
.
j
=
1
But both sides are
+
1or
−
1 and
p
i
is an odd prime. Therefore this must be an equality.
Thus for any
b
we have
r
=···=
=
b
j
.
f
1
(
b
1
)
f
r
(
b
r
)
j
=
1
Clearly this cannot happen unless
r
1: once we have at least two factors, we know
that the
b
i
's are totally independent, so we can just fix
b
i
for
i
=
1 and make
b
1
change,
and we obtain that
f
2
(
b
2
) must depend on
b
1
, which is a contradiction. Hence
r
>
=
1,
which means that
n
is a prime number.
7.1.4 Miller-Rabin Test
We conclude this section with the
Miller-Rabin test
which generalizes the Fermat test
and the Solovay-Strassen test. It is depicted in Fig. 7.3. We can prove that it always
Search WWH ::
Custom Search