Fermat primality test
E530310
The Fermat primality test is a probabilistic algorithm that checks whether a number is prime by verifying congruences derived from Fermat's little theorem.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Solovay–Strassen primality test | 1 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
Monte Carlo algorithm
ⓘ
primality test ⓘ probabilistic algorithm ⓘ |
| assumes | Fermat's little theorem holds for primes ⓘ |
| basedOn | Fermat's little theorem NERFINISHED ⓘ |
| canBeRepeatedWith | multiple random bases ⓘ |
| canMisclassify | Carmichael numbers as probably prime ⓘ |
| canUseBase | small fixed bases for some ranges of n ⓘ |
| coreCondition | a^(n-1) ≡ 1 (mod n) ⓘ |
| defines |
Fermat liar base
ⓘ
Fermat witness base ⓘ |
| errorSide | primality side ⓘ |
| failsOn | Carmichael numbers for many bases ⓘ |
| falseNegativeMeaning | prime reported as composite does not occur ⓘ |
| falsePositiveMeaning | composite reported as probably prime ⓘ |
| guarantees | if a^(n-1) ≢ 1 (mod n) then n is composite ⓘ |
| hasAdvantage |
simple to implement
ⓘ
very fast for large integers ⓘ |
| hasDisadvantage |
can be fooled by Carmichael numbers
ⓘ
error probability not easily bounded without base restrictions ⓘ |
| hasErrorType | false positive ⓘ |
| hasInput |
integer base a with 1 < a < n
ⓘ
integer n > 2 ⓘ |
| hasProperty | one-sided error ⓘ |
| hasSpecialComposite | Carmichael number ⓘ |
| isDeterministicFor | prime inputs ⓘ |
| isExampleOf | randomized primality test ⓘ |
| isIntroducedInContextOf | computational number theory ⓘ |
| isLessReliableThan |
Miller–Rabin primality test
ⓘ
Solovay–Strassen primality test NERFINISHED ⓘ |
| isPredecessorOf | strong probable prime tests ⓘ |
| isProbabilisticBecause | some composite numbers pass the test ⓘ |
| isRandomizedFor | composite detection with random bases ⓘ |
| isRelatedTo | Fermat pseudoprime NERFINISHED ⓘ |
| isSimplerThan |
AKS primality test
NERFINISHED
ⓘ
Miller–Rabin primality test NERFINISHED ⓘ |
| isTaughtIn |
algorithms courses
ⓘ
computational number theory courses ⓘ |
| isUsedAs | fast preliminary primality filter ⓘ |
| isUsedIn | cryptographic key generation heuristics ⓘ |
| neverProduces | false negative for primality ⓘ |
| outputs | composite or probably prime ⓘ |
| repetitionEffect | reduces probability of error ⓘ |
| timeComplexity | polynomial in log n ⓘ |
| typicalBaseChoice | random integer in [2, n−2] ⓘ |
| usesConcept |
congruence
ⓘ
modular arithmetic ⓘ |
| usesOperation | modular exponentiation ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Solovay–Strassen primality test