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

) ∗ , namely a primitive
root modulo n (see page 480). Furthermore, it can be demonstrated that if we
have a factorization of n

since the test finds an element of order n − 1in( Z /n Z

1 and n is prime, then the above primality test can
be employed to prove that n is prime in polynomial time; but if n is composite
the algorithm will run without bound, or diverge .
Primality proofs sacrifice one of speed or generality. For instance, there is
the Lucas-Lehmer test for Mersenne numbers, Pocklington's theorem, Proth's
theorem, and Pepin's theorem, all of which the reader may see in detail by
consulting [169, Chapter 4, pp. 180-184], for instance.
We will be concerned herein with tests that are used in practice. Usually,
these are tests that are simple, generally applicable, and eGcient, but unlike the
aforementioned tests, they sometimes fail. These are the compositeness tests.
Note that in a compositeness test, failure of the test means that n does not
satisfy the condition for compositeness and n is composite. In other words,
failure results in a composite number being indicated as a prime, but never is a
prime indicated as a composite number. The reason is that the condition is a
“proof of compositeness” in the sense that if the condition is satisfied, n is forced
to be composite. However, the converse is false. Composite numbers may fail
to satisfy the condition. We may again employ the converse of Fermat's little
theorem as an illustration.

−

Fermat's Little Theorem as a Compositness Test
If n ∈ N , a ∈ Z with gcd( a,n ) = 1, and

a n − 1 ≡ 1 (mod n ) , (F.1)

then n is composite.
Note that any n satisfying condition (F.1) must be composite by Fermat's
little theorem. An application of the above is an interpretation of Lucas' test as
a compositeness test by letting n be odd and a = 2. See [46]for a recent article
by John Brillhart on this famous test by Lucas. He argues that a primality test
is an algorithm “whose steps verify the hypothesis of a theorem whose conclusion
is “ n is prime.” which is consistent with our definition.
If n fails condition (F.1), then this is not a proof that n is prime.

For

instance, 2 340

31. Such numbers that fail condition
(F.1), and are composite are called pseudoprimes . In fact, there are composite
numbers for which the choice of the base a is irrelevant in the sense that they
will always fail the test.

≡ 1 (mod 341), yet 341 = 11 ·

For instance, a 541

≡ a (mod 541) for any a ∈ Z ,

yet 561 = 3 17. This is an example of a Carmichael number or absolute

pseudoprime . Moreover, there are known to be infinitely many Carmichael
numbers (see [7]). This shows, in the extreme, that Fermat's little theorem may
not be used as a primality test . However, the following is a well-known and
utilized primality test. The presentation is taken from [170].

· 11 ·