PlanetMath: Fermat compositeness test

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (231)
Orphanage
Unclass'd
Unproven (514)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Fermat compositeness test

(Algorithm)

The Fermat compositeness test is a primality test based on the observation that by Fermat's little theorem if $b^{n-1} \not\equiv 1\pmod n$ and $b\not\equiv 0\pmod n$ , then is composite. The Fermat compositeness test consists of checking whether $b^{n-1} \equiv 1\pmod n$ for a handful of values of . If a with $b^{n-1} \not\equiv 1\pmod n$ is found, then is composite.

A value of for which $b^{n-1} \not\equiv 1\pmod n$ is called a witness to 's compositeness. If $b^{n-1} \equiv 1\pmod n$ , then is said to be pseudoprime base .

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 A002997 for a list of first few Carmichael numbers).

"Fermat compositeness test" is owned by bbukh. [ full author list (2) | owner history (1) ]

(view preamble | get metadata)