Appendix F: Recognizing Primes - Codes: The Guide to Secrecy from Ancient to Modern Times - page 549

Appendix F: Recognizing Primes

F.1 Primality and Compositeness Tests

The methods in Appendix C for factoring might be considered a means for
recognizing primes if an attempt to factor n fails. Of course, we need only look
at odd integers, so f or instance, we could simply trial divide n by all odd integers
between 2 and √ n . However, if n is a 100-digit integer, say, then this would
take longer than the life of the universe!
In general, factorization methods are quite time consuming, whereas deciding
whether a given n is composite or prime is much more eGcient. Part of the
reason is that a test for recognizing primes, which are not attempts to factor n ,
and which determine n to be composite, do not provide the factors of n .Two
tests for recognizing primes are given as follows.
(1) The test has a condition for compositeness. If n satisfies the condition, then
n must be composite. If n fails the condition, it might still be composite
(with low probability). In other words, a successful completion of the
test — satisfying the condition — always guarantees that n is composite;
whereas an unsuccessful completion of the test — failing to satisfy the
condition — does not prove that n is prime.

(2) The test has a condition for primality. If n satisfies the condition, then n
must must be prime. If it fails the condition, then n must be composite.

We call (1) a compositeness test and (2) a primality test .
Factorization methods may be used as compositeness tests, but quite expen-
sive ones, as we discussed above. Thus, they may be used only as compositeness
tests, and only to find very small factors.
Primality tests, as we have defined them, are sometimes called primality
proofs , which are typically either complicated to apply or else are applicable only
to special numbers such as Fermat numbers, those of the form 2 2 n + 1. In other
words, they sacrifice either speed or generality, but always provide a correct
answer without failure. We look at one, which employs the converse of Fermat's
little theorem (see Corollary A.2 on page 479). The following is attributable to
D.H. Lehmer, M. Kraitchik, and others (see page 511 in Appendix C).

Primality Test via the Converse of Fermat's Little Theorem
Suppose that n ∈ N with n ≥ 3. Then n is prime if and only if there exists

such that m n − 1 1 (mod n ), but m ( n − 1) /q an m ∈ N ≡ ≡ 1 (mod n ) for any

prime q ( n

− 1).

A major pitfall with the above primality test is that we must have knowledge
of a factorization of n

1, so it works well on special numbers such as Fermat
numbers, for instance. However, the above is a general “proof” that n is prime

−