Deciding primality is easy; producing the factors is not
Primality testing is in polynomial time; no polynomial-time factoring algorithm is known. The gap is not a matter of degree — it is the foundation of public-key cryptography. Within primality work there is a further distinction that must never be blurred: a compositeness test can prove a number composite but never prove it prime, while a primality proof produces a verifiable certificate. Fast probabilistic tests do the first; slower algorithms do the second.
Learning objectives
- Distinguish compositeness tests, probable primes and primality proofs.
- Explain why a witness to compositeness is not a factor.
- Select a testing strategy appropriate to the application.
- Interpret a primality certificate and its verification cost.
- State the status of AKS and why it is not used in practice.
Section 01The asymmetry
AKS settled this unconditionally in 2002. In practice a Miller–Rabin screen followed by ECPP proves primality for thousands of digits routinely.
The number field sieve runs in L[1/3]. No polynomial-time classical algorithm is known, and the presumed hardness underpins RSA.
Miller–Rabin can certify that a 2048-bit number is composite in milliseconds while giving no information whatsoever about its factors. The test detects a structural failure of a property that primes have; it does not decompose anything. Conflating the two is the single most common misunderstanding in this area.
Section 02Three levels of assurance
| Level | Output | Guarantee | Cost |
|---|---|---|---|
| Compositeness test | Composite, or no conclusion | Composite is certain; the other outcome proves nothing | One modular exponentiation per round |
| Probable prime | Passed k independent rounds | Error probability below 4−k for random bases | k modular exponentiations |
| Primality proof | Prime, with a certificate | Certain, and independently verifiable | Substantially higher — but verification is cheap |
A pseudoprime is a composite that passes a given test for a given base. Carmichael numbers pass the Fermat test for every base coprime to them, which is why Fermat alone is inadequate; the strong test of Miller–Rabin has no such universal counterexamples.
For cryptographic key generation, probable primality at a suitable round count is standard and accepted. For a published mathematical claim, for a record computation, or wherever a third party must be able to check the result, a certificate is required. The distinction should be recorded with the number, not left implicit.
Section 03Strategy
- Stage 01Cheap rejectionTrial division by small primes removes the great majority of composites almost for free.
- Stage 02Strong probable prime testA few Miller–Rabin rounds, or a Baillie–PSW combination, eliminate essentially everything else.
- Stage 03Decide the requirementIf probable primality suffices, stop here. If proof is needed, continue.
- Stage 04ProvePocklington if the factorisation of n−1 is partly known; otherwise ECPP, or the Jacobi sum test for numbers up to a few thousand digits.
- What is the number for?
- Cryptographic key Strong probable prime — standard practice, with the round count set by the applicable standard.
- Published result ECPP certificate — independently verifiable by a third party.
- Special form, e.g. 2p−1 Lucas–Lehmer — a specialised deterministic test, far faster than any general method.
- Small, under 64 bits Deterministic Miller–Rabin — verified base sets make the test deterministic in this range.
Section 04AKS and its place
The AKS algorithm decides primality in deterministic polynomial time without any unproven hypothesis — a landmark theoretical result that resolved a long-standing open question.
Even with substantial improvements the exponent remains high enough that AKS is far slower than ECPP or the Jacobi sum test on numbers of any practical size. Its importance is that it settled the complexity of the problem; it did not change how primality is established in practice.
- 1976MillerA deterministic polynomial-time test, conditional on the extended Riemann hypothesis.
- 1980RabinThe randomised strong probable prime test — still the workhorse of every implementation.
- 1983Adleman, Pomerance and RumelyThe Jacobi sum test, with a running time barely superpolynomial; the first practical general proving method.
- 1986Goldwasser–Kilian, then Atkin–MorainElliptic curve primality proving, producing short certificates that verify quickly.
- 2002Agrawal, Kayal and SaxenaAKS: deterministic, unconditional, polynomial time.
ReferenceFrequently asked questions
Why can a compositeness test never prove primality?
Because it checks a property that all primes have but that some composites also have. Failing the check proves compositeness; passing it merely places the number in a set containing all primes and some composites.
How many Miller-Rabin rounds are enough?
For random candidates the error probability falls much faster than the worst-case 4^(-k) bound suggests, and standards typically specify between 20 and 64 rounds depending on size and application. For adversarially chosen inputs the worst-case bound is what applies, so random base selection is essential.
What is a primality certificate?
A short piece of data allowing anyone to verify primality far more cheaply than discovering it. For Pocklington it is a partial factorisation of n−1 with a suitable base; for ECPP it is a chain of curves and points that reduces primality of n to primality of a smaller number.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.