False witnesses

Fermat's primality test

Fermat's little theoremsays that ifpis a prime andais not a multiple ofp, then

a^p-1= 1 (modp).

The contrapositive of Fermat's little theorem says if

a^p-1 1 (modp)

then eitherp is not prime ora is a multiple ofp. The contrapositive is used to test whether a number is prime. Pick a numbera less thanp (and soa is clearly not a multiple ofp) and compute a^p-1mod p. If the result is not congruent to 1 mod p, thenp is not a prime.

So Fermat's little theorem gives us a way to prove that a number is composite: if a^p-1 mod p equals anything other than 1, p is definitely composite. But if a^p-1 mod p does equal 1, the test is inconclusive. Such a resultsuggests thatp is prime, but it might not be.

Examples

For example, suppose we want to test whether 57 is prime. If we apply Fermat's primality test witha = 2 we find that 57 is not prime, as the following bit of Python shows.

 >>> pow(2, 56, 57) 4

Now let's test whether 91 is prime usinga = 64. Then Fermat's test is inconclusive.

 >>> pow(64, 90, 91) 1

In fact 91 is not prime because it factors into 7 * 13.

If we had useda = 2 as our base we would have had proof that 91 is composite. In practice, Fermat's test is applied with multiple values ofa (if necessary).

Witnesses

If a^p-1= 1 (modp), thena is awitness to the primality ofp. It's not proof, but it's evidence. It's still possiblep is not prime, in which casea is afalse witness to the primality ofp, orp is apseudoprime to the basea. In the examples above, 64 is a false witness to the primality of 91.

Until I stumbled on a paper [1] recently, I didn't realize that on average composite numbers have a lot of false witnesses. For large N, the average number of false witnesses for composite numbers less than N is greater than N^15/23. Although N^15/23 is big, it's small relative toN when N is huge. And in applications, N is huge, e.g. N = 2²⁰⁴⁸ for RSA encryption.

However, your chances of picking one of these false witnesses, if you were to choose a base a at random, is small, and so probabilistic primality testing based on Fermat's little theorem is practical, and in fact common.

Note that the result quoted above is a lower bound on the average number of false witnesses. You really want an upper bound if you want to say that you're unlikely to run into a false witness by accident. The authors in [1] do give upper bounds, but they're much more complicated expressions than the lower bound.

Related posts

• Fast exponentiation
• Testing for primes less than a quintillion
• What does it mean to say a number is probably prime?

[1] Paul Erds and Carl Pomerance. On the Number of False Witnesses for a Composite Number. Mathematics of Computation. Volume 46, Number 173 (January 1986), pp. 259-279.

The post False witnesses first appeared on John D. Cook.