Cryptography Reference
In-Depth Information
Trial Division
The simplest (deterministic) primality testing algorithm for a positive integer
n
∈
N
is to test whether there exists a prime between 2 and
√
n
that divides
n
.Ifsucha
number exists, then
n
is not prime (i.e., it is composite) and the algorithm can abort.
If, however, such a number does not exist, then
n
is prime. In the literature, this
algorithm is commonly referred to as
trial division
. It requires a list of known prime
numbers between 2 and
√
n
. As a consequence of the prime density theorem (i.e.,
Theorem 3.4), one must perform
√
n
ln
√
n
trial divisions to show that
n
is a prime. For example, in a typical cryptographic
setting,
n
is larger than 10
75
. In this case, one must perform
√
10
75
ln
√
10
75
10
35
>
3
.
5
·
trial divisions. This is computationally infeasible, and hence the trial division al-
gorithm cannot be used for numbers of a certain size. All major primality testing
algorithms that work for large numbers are probabilistic.
Fermat Test
In the 17th century, Pierre de Fermat
19
proved Theorem 3.7 (also known as Fermat's
Little Theorem), which can be turned into a simple primality testing algorithm.
Fermat's Little Theorem states that for any prime number
p
and any number
a
not
divisible by
p
, the equivalence
a
p−
1
1(mod
p
) must hold. Consequently, one
can test the primality—or rather the compositeness—of
n
by randomly choosing
avaluefor
a
(not divisible by
n
) and computing
a
n−
1
(mod
n
). If this value is
not equal to 1,then
n
is definitively not a prime (and we have found a witness for
the compositeness of
n
, respectively). Unfortunately, the converse is not true and
finding an
a
for which
a
n−
1
≡
1(mod
n
) does not imply that
n
is prime.
20
In fact,
there is an entire class of composite numbers for which
a
n−
1
≡
≡
1(mod
n
) holds
19
Pierre de Fermat was a French mathematician who lived from 1607 to 1665.
20
For this reason, the Fermat test (and the two other tests mentioned later) is referred to as a
compositeness test.
