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