Miller primality test
E735950
The Miller primality test is a randomized algorithm used to determine whether a number is prime with high confidence, forming the basis of the widely used Miller–Rabin primality test in computational number theory and cryptography.
Observed surface forms (3)
| Surface form | Occurrences |
|---|---|
| Miller–Rabin primality test | 1 |
| Probabilistic Algorithm for Testing Primality | 1 |
| Rabin–Miller primality test | 1 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm in number theory
ⓘ
primality test ⓘ randomized algorithm ⓘ |
| application |
cryptographic parameter generation
ⓘ
key generation in public-key cryptography ⓘ testing large integers for primality ⓘ |
| assumption | generalized Riemann hypothesis for certain error bounds ⓘ |
| author | Gary L. Miller NERFINISHED ⓘ |
| basedOn | Riemann hypothesis NERFINISHED ⓘ |
| classification | Monte Carlo algorithm NERFINISHED ⓘ |
| compositenessWitnessCondition | x ≠ 1 and x ≠ n−1 and no square equals n−1 modulo n ⓘ |
| coreIdea |
search for nontrivial square roots of 1 modulo n
ⓘ
use repeated squaring of a^d mod n ⓘ |
| deterministicUnder | generalized Riemann hypothesis ⓘ |
| errorDirection |
may classify some composite numbers as probably prime
ⓘ
never classifies a prime as composite ⓘ |
| errorType | one-sided error ⓘ |
| field |
computational number theory
ⓘ
cryptography ⓘ |
| generalizationOf | Fermat primality test ⓘ |
| guarantee |
deterministic polynomial-time primality test under GRH
ⓘ
never declares a composite number prime if the generalized Riemann hypothesis holds ⓘ |
| improvesOn | Fermat primality test NERFINISHED ⓘ |
| influenced | practical primality testing algorithms ⓘ |
| input | odd integer n > 2 ⓘ |
| inspired | Miller–Rabin primality test NERFINISHED ⓘ |
| language | number-theoretic algorithm ⓘ |
| output | "composite" or "probably prime" ⓘ |
| relatedAlgorithm | AKS primality test NERFINISHED ⓘ |
| relatedConcept |
Carmichael number
ⓘ
strong pseudoprime ⓘ witness for compositeness ⓘ |
| relation | forms the theoretical basis of the Miller–Rabin primality test ⓘ |
| step |
check if x = 1 or x = n−1
ⓘ
choose random base a with 1 < a < n−1 ⓘ compute x = a^d mod n ⓘ square x repeatedly up to s−1 times ⓘ write n−1 = 2^s·d with d odd ⓘ |
| timeComplexity | polynomial in log n under GRH ⓘ |
| typicalImplementationLanguage |
C
ⓘ
C++ NERFINISHED ⓘ Java NERFINISHED ⓘ Python NERFINISHED ⓘ |
| usedWith | modular exponentiation by repeated squaring ⓘ |
| uses |
decomposition of n−1 as 2^s·d
ⓘ
modular exponentiation ⓘ witnesses for compositeness ⓘ |
| yearProposed | 1976 ⓘ |
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Michael O. Rabin
this entity surface form:
Rabin–Miller primality test
subject surface form:
Michael O. Rabin
this entity surface form:
Probabilistic Algorithm for Testing Primality
this entity surface form:
Miller–Rabin primality test