Cryptography Reference
In-Depth Information
theorem
, formulated as a conjecture by A. M. Legendre, that the number
π
(
x
)
of
primes
p
,
2
≤ p ≤ x
, approaches
x/
ln
x
asymptotically as
x
goes to infinity (see,
for example, [Rose], Chapter 12).
8
A few values of the number of primes less than
agiven
x
will help to make clear the size of numbers we are dealing with. Table
10-2 gives the values of both
π
(
x
)
, the actual number of primes less than or equal
to
x
, and the asymptotic approximation
x/
ln
x
. The question mark in the last cell
indicates a number to be filled in by the reader. ;-)
Table 10-2. The number of primes up to various limits
x
10
2
10
4
10
8
10
16
10
18
10
100
x
x/
ln
x
10
97
4
×
22
1,086
5,428,681
271,434,051,189,532
24,127,471,216,847,323
π
(
x
)
25
1,229
5,761,455
279,238,341,033,925
24,739,954,287,740,860
?
The number of necessary calculations for the division test of
x
grows almost
with the number of digits of
x
in the exponent. Therefore, the division test alone
is not a practicable method for determining the primality of large numbers.
We shall see, in fact, that the division test is an important aid in connection
with other tests, but in principle we would be content to have a test that gave
information about the primality of a number without revealing anything about its
factorization. An improvement in the situation is offered by the little theorem of
Fermat, which tells us that for a prime
p
and all numbers
a
that are not multiples
of
p
the congruence
a
p
−
1
≡
1mod
p
holds (see page 177).
From this fact we can derive a primality test, called the Fermat test: If for
some number
a
we have
gcd(
a, n
)
=1
or
gcd(
a, n
)=1
and
1
≡ a
n
−
1
mod
n
,
then
n
is composite. An exponentiation
a
n
−
1
≡
1mod
n
requires
O
log
3
n
CPU operations, and experience indicates that in only a few tries a composite
number will reveal its lack of primality. However, there are exceptions, and these
limit the utility of the Fermat test. Therefore, we shall have to have a closer look at
them.
We must face the fact that the converse of Fermat's little theorem does
not hold: Not every number
n
with
gcd(
a, n
)=1
and
a
n
−
1
≡
1mod
n
for
1
1
is prime. There exist composite numbers
n
that pass the Fermat
test as long as
a
and
n
are relatively prime. Such numbers are called Carmichael
numbers, named for their discoverer, Robert Daniel Carmichael (1879-1967). The
smallest of these curious objects are
≤
a
≤
n
−
561=3
·
11
·
17
,
1105 = 5
·
13
·
17
,
1729 = 7
·
13
·
19
.
All Carmichael numbers have in common the property that each of them
possesses at least three different prime factors (see [Kobl], Chapter 5). It was only
8
The prime number theorem was proved independently in 1896 by Jacques Hadamard and
Charles-Jacques de la Vallée Poussin (see [Bund], Section 7.3).
