Fermat pseudoprime
E530313
A Fermat pseudoprime is a composite number that nevertheless satisfies Fermat's little theorem for a given base, making it appear prime under that specific primality test.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
composite number
ⓘ
number theory concept ⓘ pseudoprime ⓘ |
| appearsAs | prime under Fermat primality test for a specific base ⓘ |
| appearsIn |
computational number theory literature
ⓘ
cryptographic security analyses ⓘ |
| contrastsWith |
Carmichael number that is pseudoprime to all coprime bases
ⓘ
prime number that satisfies Fermat's little theorem for all coprime bases ⓘ |
| definedAs | composite integer n such that a^n ≡ a (mod n) for some integer base a coprime to n ⓘ |
| dependsOn | choice of base a ⓘ |
| failsToBe | prime number ⓘ |
| field | number theory ⓘ |
| generalizationOf | base-specific pseudoprime concepts ⓘ |
| hasAlternativeName | Fermat liar for base a (for the base that makes it pass the test) ⓘ |
| hasBaseSpecificForm |
Fermat pseudoprime to base 10
ⓘ
Fermat pseudoprime to base 2 ⓘ Fermat pseudoprime to base 3 ⓘ Fermat pseudoprime to base 5 ⓘ Fermat pseudoprime to base a ⓘ |
| hasCardinalityProperty | infinitely many Fermat pseudoprimes are known for many bases ⓘ |
| hasExample |
1105
ⓘ
1729 ⓘ 2152302898747 ⓘ 2465 ⓘ 2821 ⓘ 3215031751 ⓘ 341 ⓘ 341550071728321 ⓘ 41041 ⓘ 561 ⓘ 645 ⓘ 6601 ⓘ 825265 ⓘ 8911 ⓘ |
| hasProperty | passes a base-a Fermat primality test despite being composite ⓘ |
| hasTestingIssue | can cause Fermat primality test to falsely label a composite as prime ⓘ |
| hasUnresolvedQuestion | distribution of Fermat pseudoprimes for various bases ⓘ |
| isSubsetOf | composite integers that pass some primality test ⓘ |
| namedAfter | Pierre de Fermat NERFINISHED ⓘ |
| relatedTo |
Carmichael number
ⓘ
Fermat primality test NERFINISHED ⓘ Miller–Rabin primality test NERFINISHED ⓘ probabilistic primality testing ⓘ strong pseudoprime ⓘ |
| requires | gcd(a,n) = 1 for the base a and integer n ⓘ |
| satisfies | Fermat's little theorem for a given base ⓘ |
| usedIn |
analysis of reliability of Fermat primality test
ⓘ
construction of counterexamples to naive primality tests ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.