Fermat primality test

Fermat's little theorem states that if p is prime and a is coprime to p, then a^p-1 - 1 is divisible by p. This can also be written, a^p-1 = 1 (mod p). It turns out that the converse of this theorem is usually true: if p is composite, then a^p-1 is unlikely to be congruent to 1 mod p for an arbitrary value of a.

The encryption program PGP takes advantage of this property of the theorem to test whether the large random numbers it selects are prime. It tests the values we'll call x using 4 values of a (referred to as witnesses) using the above formula. These 4 values are 2, 3, 5 and 7, the first four primes. If 1 = 2^x-1 = 3^x-1 = 5^x-1 = 7^x-1 (mod x), it knows that the number x is probably prime. If any of the equations comes up with a value other than 1, then x is definitely composite. Using additional witnesses decreases the chance that a composite x will appear to be prime, although very few large numbers can fool the 4 witnesses already listed.

The pseudoprime article gives an in-depth discussion of numbers which fool primality tests such as these.