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
Tom Waits

... and "Bad Liver and a Broken Heart" cemented his hard living reputation, with a lyrical style pitched somewhere between Raymond Chandler and Charles Bukowski. Foreign ...