Modern Factoring Methods
ECM Stage Two and Practical Tuning
ECM stage two, the large prime search, and how the two bounds are tuned together.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0671
Stage two handles the common case where the curve order is smooth except for one prime above the stage one bound. Searching for that single prime is far cheaper than extending stage one to cover it.
The situation
After stage one the point has been multiplied by every prime power below the first bound. If the order equals that smooth part times one larger prime, multiplying by that prime completes the job.
The search
ECM stage two
- Take the stage one resultThe point after multiplication by the smooth scalar.
- Precompute small multiplesA table of multiples spanning the step size.
- Step through the rangeGiant steps across the interval between the bounds.
- Accumulate differencesMultiply coordinate differences together rather than taking a GCD each time.
- Take one GCDAt the end of the accumulation.
Tuning the two bounds
| Bound | Controls | Typical relation |
|---|---|---|
| Stage one bound | The smooth part covered | Set by target factor size |
| Stage two bound | The single large prime range | Commonly around a hundred times the first |
How many curves
The expected number of curves needed for a factor of a given size is computed from the smoothness probability at the chosen bounds. Tables of recommended bounds and curve counts by digit size are standard and should be used rather than derived.
Improvements
Brent-Suyama extension
Uses polynomial evaluation to cover the stage two range more efficiently, effectively extending the reach for the same work.
Batch stage two
Runs stage two for many curves together, sharing the precomputed tables.
FFT-based stage two
Uses fast polynomial arithmetic to evaluate many candidates at once; the standard approach in high-performance implementations.
Where ECM fits
ECM is used to strip medium factors before a sieve is applied, and to factor the cofactors arising in smoothness testing. See method comparison.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.3.4. 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.