Software, Tables and Sources
Modern Factoring Methods Compared
Comparing factoring methods by target size, expected factor size and available hardware, with a practical sequencing recommendation.
Engineering / MathematicsSoftware, Tables and Sources2 min readKV-MATH-0680
Factoring method selection turns on two independent questions: how large the target is, and how large the factors are expected to be. Conflating them is the commonest mistake.
The two axes
Method summary
| Method | Cost depends on | Best for |
|---|---|---|
| Trial division | The smallest factor | Factors below about a million |
| Pollard rho | The smallest factor | Factors up to about 12 digits |
| SQUFOF | The target | Targets up to about 18 digits; very small constants |
| Pollard p-1 | Smoothness of one less than the factor | A cheap opportunistic attempt |
| ECM | The factor found | Factors from 15 to about 60 digits |
| MPQS or SIQS | The target | Targets up to about 100 digits |
| Number field sieve | The target | Targets beyond about 100 digits |
Recommended sequencing
Practical factoring sequence
- Trial divideTo a modest bound; clears most inputs instantly.
- Test for primalityWith Baillie-PSW — never factor a prime.
- Check for a perfect powerSee perfect power detection.
- Run Pollard rho brieflyCheap; catches small factors.
- Run p-1 brieflyCheap and occasionally spectacular.
- Run ECM at increasing boundsStrips medium factors; stop when the expected effort exceeds the sieve cost.
- Apply a sieveSIQS or the number field sieve by target size.
- Recurse on cofactorsEach factor found must itself be tested and factored.
Knowing when to stop with ECM
Hardware
| Stage | Parallelism |
|---|---|
| ECM | Perfect; curves are independent |
| Sieving | Excellent; intervals are independent |
| Sieve linear algebra | Poor; needs tight coupling |
| Number field sieve square root | Limited |
Special forms
Targets of special algebraic shape admit far better polynomials and are factored well beyond the general record size. Always check whether a target has such a form before treating it as general.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10. 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.