PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (27)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
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 $ n$ is composite. The Fermat compositeness test consists of checking whether $ b^{n-1} \equiv 1\pmod n$ for a handful of values of $ b$. If a $ b$ with $ b^{n-1} \not\equiv 1\pmod n$ is found, then $ n$ is composite.

A value of $ b$ for which $ b^{n-1} \not\equiv 1\pmod n$ is called a witness to $ n$'s compositeness. If $ b^{n-1} \equiv 1\pmod n$, 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 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)

View style:

See Also: Miller-Rabin prime test

Also defines:  pseudoprime, witness, Carmichael numbers
Keywords:  primality, prime, composite, number theory
Log in to rate this entry.
(view current ratings)

Cross-references: sequence, OEIS, base, composite, Fermat's little theorem, primality
There are 10 references to this entry.

This is version 12 of Fermat compositeness test, born on 2002-12-20, modified 2007-03-13.
Object id is 3781, canonical name is FermatCompositenessTest.
Accessed 6942 times total.

Classification:
AMS MSC: 11A51 (Number theory :: Elementary number theory :: Factorization; primality)
Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)