Modern Factoring Methods
Smoothness and Sub-exponential Complexity
Smooth numbers, the Dickman function, and how balancing smoothness probability against factor base size produces sub-exponential running times.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0665
Almost every modern factoring and class group algorithm rests on the same calculation: how likely a random number is to factor entirely over a fixed set of small primes, and how to choose that set optimally.
Smooth numbers
- B-smooth
- An integer all of whose prime factors are at most B.
- Semi-smooth
- Smooth except for one prime slightly above the bound. Exploited by the large prime variation.
- Smoothness probability
- The proportion of integers up to a size that are smooth to a given bound.
The Dickman estimate
The proportion of integers up to a bound that are smooth to a considerably smaller bound is estimated by the Dickman function, evaluated at the ratio of the logarithms.
The optimisation
A larger factor base makes each candidate more likely to be smooth but requires more relations and a larger matrix. Balancing the two costs gives the optimal bound.
Optimising the smoothness bound
- Write down the two costsSearch cost is the reciprocal of the smoothness probability, times the number of relations needed.
- DifferentiateWith respect to the smoothness bound.
- SolveThe balance point gives the optimal bound and the resulting complexity.
L-notation
| Algorithm | Complexity |
|---|---|
| CFRAC | L(1/2) |
| Quadratic sieve | L(1/2) |
| ECM | L(1/2) in the size of the factor, not the number |
| Number field sieve | L(1/3) |
| Class group methods | L(1/2) in the discriminant |
Why the number field sieve is better
The sieves examine values of a polynomial. The quadratic sieve's values are around the square root of the number; the number field sieve's are far smaller, so they are much more likely to be smooth. That improvement is what moves the exponent from one half to one third.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.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.