Randomization - Data Structures and Problem Solving Using Java - page 409

randomized primality testing

9.6

Recall that in Section 7.4 we described some numerical algorithms and
showed how they could be used to implement the RSA encryption scheme. An
important step in the RSA algorithm is to produce two prime numbers p and
q . We can find a prime number by repeatedly trying successive odd numbers
until we find one that is prime. Thus the issue boils down to determining
whether a given number is prime.

The simplest algorithm for primality testing is trial division. In this algo-
rithm, an odd number greater than 3 is prime if it is not divisible by any other
odd number smaller than or equal to

Trial division is the
simplest algorithm
for primality test-
ing. It is fast for
small (32-bit) num-
bers but cannot be
used for larger
numbers.

N . A direct implementation of this

strategy is shown in Figure 9.8.
Trial division is reasonably fast for small (32-bit) numbers, but it is unus-
able for larger numbers because it could require the testing of roughly
divisors, thus using time. 2 What we need is a test whose running time
is of the same order of magnitude as the power routine in Section 7.4.2. A
well-known theorem, called Fermat's Little Theorem, looks promising. We
state and provide a proof of it in Theorem 9.1 for completeness, but the proof
is not needed for an understanding of the primality-testing algorithm.

N ⁄ 2

ON ( )

, then A P - 1

Theorem 9.1

Fermat's Little Theorem: If P is prime and 0 << AP ≡ 1(mod P ) .

Proof

Consider any . Clearly, Ak ≡ 0(mod P ) is impossible because P is prime and
is greater than A and k . Now consider any . would imply
, which is impossible by the previous argument because
. Thus the sequence , when considered (mod P ) , is a
permutation of . The product of both sequences (mod P ) must be
equivalent (and non-zero), yielding the equivalence A P - 1 ( P - 1)! ≡ ( P - 1)! (mod P )
from which the theorem follows.

1 ≤ kP <

1 ≤ i << j P Ai ≡ Aj mod P ( )

Aj i ( - ) ≡ 0 mod P ( )

1 ≤ ji - < P A 2 A , , … , ( P - 1 ) A

12… ,, , P - 1

If the converse of Fermat's Little Theorem were true, then we would have
a primality-testing algorithm that would be computationally equivalent to
modular exponentiation (i.e., O (log N ) ). Unfortunately, the converse is not
true. For example, 2 340

Fermat's Little The-
orem is necessary
but not sufficient to
establish primality.

≡ 1(mod 341), but 341 is composite (11

× 31).

2. Though N may seem small, if N is a 100-digit number, then N is still a 50-digit num-

ber; tests that take ON ( ) time are thus out of the question for the BigInteger type.