Fermat compositeness test
The Fermat compositeness test is a primality test based on the observation that by Fermat’s little theorem if and , then is composite. The Fermat compositeness test consists of checking whether for a handful of values of . If a with is found, then is composite.
It can be proven that most composite numbers can be shown to be composite by testing only a few values of . 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|
|Date of creation||2013-03-22 13:17:36|
|Last modified on||2013-03-22 13:17:36|
|Last modified by||bbukh (348)|