Modern Factoring Methods
The Elliptic Curve Method: Stage One
ECM stage one: multiplying a point by a highly smooth scalar to reach the identity in one component.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0670
Stage one of ECM multiplies a point by a scalar containing every prime power below a bound. If the curve order in one component divides that scalar, the component reaches the identity and the factor appears.
The scalar
The procedure
ECM stage one
- Choose a curve and pointBy Suyama's parametrisation, so a point is known without a square root.
- Build the scalarOr multiply by each prime power in turn, which avoids forming an enormous integer.
- MultiplyUsing the Montgomery ladder in projective coordinates.
- Take a GCDOf the final coordinate with the modulus.
- Interpret or continueA factor, a restart, or proceed to stage two.
Choosing the bound
| Target factor size | Typical bound | Curves needed |
|---|---|---|
| 15 digits | Small | Tens |
| 25 digits | Moderate | Hundreds |
| 35 digits | Large | Thousands |
| 45 digits and beyond | Very large | Tens of thousands or more |
Curve selection
Parametrisations that force small factors into the curve order improve the odds appreciably. Suyama's construction guarantees divisibility by twelve, and other families guarantee more.
Parallelism
When stage one fails
If the order is smooth except for one larger prime, stage two finds it far more cheaply than raising the stage one bound — see stage two.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.3.1-10.3.3. 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.