Resample the group until its order is smooth
Pollard's p−1 method fails when p − 1 is not smooth, and nothing can be done — the group is fixed. Lenstra replaced it with the group of an elliptic curve modulo n, whose order varies with the curve across the Hasse interval. Trying many curves eventually finds one with smooth order. Because success depends on the size of the factor rather than of n, ECM is the method of choice for finding medium-sized factors of very large numbers.
Learning objectives
- Explain why arithmetic on a curve modulo a composite reveals factors.
- Describe the two-stage structure and its bounds.
- State the complexity in terms of the factor size.
- Choose curve parameterisations that guarantee useful torsion.
- Position ECM correctly within a factoring pipeline.
Section 01Curves modulo a composite
The set of points satisfying a Weierstrass equation modulo composite n is not a group — the addition formulas require inverting x2 − x1, which may not be invertible. That failure is precisely the mechanism.
If gcd(x2 − x1, n) is non-trivial, the addition has failed — and that GCD is a factor of n. Geometrically, the points have become equal modulo p but not modulo q, so the computation has detected the difference between the two reductions.
By the Chinese remainder theorem, the curve modulo n corresponds to curves modulo each prime factor. Computing [M]P for a smooth M reaches the identity modulo p as soon as M is a multiple of the order of P in the curve group modulo p — and the inversion then fails.
Section 02The algorithm
- Choose a random curve E and a point P on it modulo n, by choosing the point first and solving for a curve coefficient. Avoids square roots modulo n, which cannot be computed without the factorisation.
- Set M ← ∏ q⌊logq B1⌋ over primes q ≤ B1.
- Compute [M]P by scalar multiplication, watching every inversion. A failed inversion yields the factor.
- If no failure occurs, run stage two: sweep primes in (B1, B2], batching GCDs.
- If still nothing, discard the curve and start again with a new one.
This is what distinguishes ECM from the sieves. A 40-digit factor of a 400-digit number is found as easily as a 40-digit factor of an 80-digit number. No sieve can say that, which is why ECM is run before any sieve.
Section 03Implementation choices
| Choice | Standard practice | Reason |
|---|---|---|
| Curve form | Montgomery curves | Scalar multiplication needs only x-coordinates; the ladder is fast and uniform |
| Parameterisation | Suyama or Edwards families | Guarantees torsion dividing the order, raising the chance of smoothness |
| Coordinates | Projective, one inversion at the end | Deferring inversion is faster — the GCD is then taken on the accumulated denominator |
| Stage two | Standard or improved continuation | Extends reach for one large prime at a fraction of stage one's cost |
| Bound selection | B1 chosen for the target factor size | Published tables give optimal B1 and expected curve counts by digit level |
With projective coordinates there are no intermediate inversions to fail, so the factor is found by taking a GCD of the accumulated Z-coordinate with n at the end of each stage. An implementation that simply ports affine code and defers inversion without adding this GCD will never find anything.
Section 04Position in the pipeline
- Stage 01After trial division and rhoSmall factors should already be gone; ECM targets the 15 to 60 digit range.
- Stage 02Escalate the boundsRun a batch of curves at a modest B1, then increase — cheap attempts first, following the standard digit-level tables.
- Stage 03Recurse on cofactorsEvery factor found must be primality tested, and composite cofactors returned to the pipeline.
- Stage 04Hand over to a sieveIf ECM has not split n after the effort appropriate to its largest plausible factor, the factors are probably balanced — switch to MPQS or NFS.
ECM handles unbalanced factorisations; the sieves handle balanced ones. An RSA modulus with two equal-sized primes is exactly the case ECM cannot help with, which is why key generation targets that shape.
ReferenceFrequently asked questions
Why choose the point before the curve?
Because constructing a curve first and then finding a point on it requires a square root modulo n, which cannot be computed without the factorisation. Choosing x, y and one coefficient and solving for the other avoids the problem entirely.
How many curves are needed?
It depends on the factor size and the bounds. Published tables give expected curve counts for each digit level — for a 40-digit factor, thousands of curves at appropriate bounds. Since curves are independent, this parallelises perfectly.
Does the torsion of the curve matter?
Yes. Parameterisations that force a torsion subgroup of order 12 or 16 make the group order divisible by that amount, raising the probability of smoothness measurably. This is why structured families are used rather than genuinely random curves.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.