  Encyclopedia > Fermat primality test

Article Content

Fermat primality test

Fermat's little theorem states that if p is prime and a is coprime to p, then ap-1 - 1 is divisible by p. This can also be written, ap-1 = 1 (mod p). It turns out that the converse of this theorem is usually true: if p is composite, then ap-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 = 2x-1 = 3x-1 = 5x-1 = 7x-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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Quebec Act ... to the open American Revolution to follow. There were several American concerns with the provisions of the Act. For one, it established the Roman Catholic church ...  