Classical Primality and Factoring
Trial Division and Lehman's Method
Trial division as the first factoring step, its cost, and Lehman's improvement on Fermat's method.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0652
Trial division is the first step of every factoring attempt and it handles the great majority of numbers encountered in practice. Knowing when to stop is what matters.
Trial division
Divide by successive small primes up to a chosen bound. Any factor below the bound is found; nothing above it is.
| Bound | Cost | Finds |
|---|---|---|
| A few hundred | Negligible | Most factors of random numbers |
| A million | Fast | Clears the vast majority of composites |
| Beyond | Diminishing returns | Better handled by ECM |
Implementation
Fermat's method
Fermat's method searches for a representation of the number as a difference of two squares, which immediately gives a factorisation.
Lehman's method
Lehman generalises Fermat by searching for a difference of squares after multiplying by a small integer, which handles unbalanced factors much better.
| Method | Cost | Best for |
|---|---|---|
| Trial division | Proportional to the smaller factor | Small factors |
| Fermat | Proportional to the gap between the factors | Nearly equal factors |
| Lehman | Cube root of the number | Guaranteed bound; small numbers |
| Pollard rho | Fourth root of the number | Moderate factors |
Practical sequencing
Factoring strategy
- Trial divideTo a modest bound.
- Test the cofactor for primalityUsing Baillie-PSW.
- Check for perfect powersSee perfect powers.
- Apply rho or ECMFor moderate factors.
- Apply a sieveFor the hard remaining cases.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.5.1-8.5.2. 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.