Cryptography Reference
In-Depth Information
x
/(φ(
n
)
ln
x
)
n
=
ln
x
. As a consequence, the expected number of draws of integers
in this residue class required to obtain a random prime
x
/
n
φ(
n
)
x
is asymptotic to
φ(
n
)
n
≤
ln
x
.
6.2 Primality Testing
From the previous discussion we know that large primes are relatively abundant so
that the only thing that remains for us to be able to find them is to have efficient
primality tests to distinguish primes from composites. We have already seen that the
sieve of Eratosthenes and trial division can be used for primality testing but these
algorithms are of exponential complexity and so they are not able to test primes
of cryptographic size (although they are useful as auxiliary components of other
algorithms). So far we have usedMaple's function
isprime
in our examples dealing
with large primes but we have not discussed how it works. In this section we are going
to look at the most common primality tests.
6.2.1 The Fermat Test and Pseudoprimes
Since the search-based primality tests considered so far are not able to deal with
primes of the size required for cryptographic use, a plausible idea is to look for
some simple formula that characterizes the primes among the integers and use it
as a primality test. But simplicity is no guarantee of efficiency and a remarkable
example is provided by Wilson's theorem and its converse, cf. [180, Theorem 2.22],
according to which, if
n
is an integer greater than 1, then
n
is prime if and only
if
. This looks simple enough but has a crucial drawback:
computing the factorial has exponential complexity and is impractical for the sizes
required for cryptographic applications (actually, Wilson's theorem as a primality
test is even less efficient than trial division, see Exercise 6.5 below).
(
n
−
1
)
!≡−
1
(
mod
n
)
Exercise 6.4
(i) Prove that if
p
is prime then
(
p
−
1
)
!≡−
1
(
mod
p
)
(Wilson's theorem). (Hint:
Z
p
which are their own inverses are 1 and
p
The only elements of
−
1. By
Z
p
collecting all the remaining elements of
in pairs formed by an element and
).)
(ii) Prove the converse of Wilson's theorem by showing that if the congruence
its inverse and multiplying them, show that
(
p
−
2
)
!≡
1
(
mod
p
(
n
−
1
)
!≡−
1
(
mod
n
)
holds, then any proper divisor of
n
must divide both
(
n
−
1
)
!
and
(
n
−
1
)
!+
1, which is impossible.
Exercise 6.5
(i) Prove that computing
mod
n
by the naive method, with each multipli-
cation followed by reduction modulo
n
, has complexity O
(
n
−
1
)
!
n
ln
2
n
(
)
.
