Classical Primality and Factoring
Primality Versus Factoring: Framing the Problems
Why proving compositeness is easy, proving primality is harder, and factoring is harder still — and what this asymmetry means in practice.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0646
Primality and factoring are frequently conflated and are entirely different problems. Deciding primality is easy; producing a factor is not, and the gap between them is what public-key cryptography rests on.
Three distinct questions
| Question | Difficulty | Typical method |
|---|---|---|
| Is this number composite? | Easy | A single strong pseudoprime test |
| Is this number prime, provably? | Moderate | ECPP or Jacobi sum |
| What are its factors? | Hard | ECM, MPQS or the number field sieve |
The asymmetry
A strong pseudoprime test on a composite number succeeds in exposing it with probability at least three quarters per random base, so a handful of bases settles compositeness beyond practical doubt. Nothing in that process yields a factor.
Probable primes versus proven primes
- Probable prime
- Passes several strong pseudoprime tests. Overwhelmingly likely prime, but not proven.
- Proven prime
- Certified by an algorithm producing a verifiable certificate.
- Industrial-grade prime
- A probable prime accepted for practical use without proof. Standard in cryptography.
Practical strategy
Practical primality determination
- Trial divideBy small primes; disposes of most composites instantly.
- Strong pseudoprime testBase two first, then a few random bases.
- Lucas testFor a Baillie-PSW combination.
- Stop or proveAccept as a probable prime, or invoke a proving algorithm if certainty is required.
When factoring is needed
Factoring appears throughout this collection as a subroutine, not merely as an end in itself: discriminant factorisation for maximal orders, norm factorisation for ideal factorisation, and smoothness testing in relation collection.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.