Fermat compositeness test

The Fermat compositeness testMathworldPlanetmath is a primality test based on the observation that by Fermat’s little theorem if bn-11(modn) and b0(modn), then n is composite. The Fermat compositeness test consists of checking whether bn-11(modn) for a handful of values of b. If a b with bn-11(modn) is found, then n is composite.

A value of b for which bn-11(modn) is called a witness to n’s compositeness. If bn-11(modn), then n is said to be pseudoprime base b.

It can be proven that most composite numbers can be shown to be composite by testing only a few values of b. However, there are infinitely many composite numbers that are pseudoprime in every base. These are Carmichael numbers (see OEIS sequence http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002997A002997 for a list of first few Carmichael numbers).

Title Fermat compositeness test
Canonical name FermatCompositenessTest
Date of creation 2013-03-22 13:17:36
Last modified on 2013-03-22 13:17:36
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 15
Author bbukh (348)
Entry type Algorithm
Classification msc 11A51
Related topic MillerRabinPrimeTest
Defines pseudoprime
Defines witness
Defines Carmichael numbers