The Elliptic Curve Method (ECM)

Executive summary

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 x₂ − x₁, which may not be invertible. That failure is precisely the mechanism.

The productive failure

If gcd(x₂ − x₁, 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

AlgorithmECM, one curvein: n, bounds B₁, B₂ → out: a factor, or restart

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^{⌊log_q B₁⌋} over primes q ≤ B₁.
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 (B₁, B₂], batching GCDs.
If still nothing, discard the curve and start again with a new one.

L_p[1/2, √2]complexity in terms of the factor p

60 digitslargest factors found in practice

Embarrassingly parallelcurves are fully independent

Cost depends on the factor, not on n

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

Practical ECM implementation
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	B₁ chosen for the target factor size	Published tables give optimal B₁ and expected curve counts by digit level

Deferred inversion changes the failure detection

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 B₁, 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.

The decisive division of labour

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.

Handbook application: from concept to controlled practice

Purpose. This expanded section turns the original page into a practical handbook. It preserves the supplied material and adds a repeatable way to apply, check and review The Elliptic Curve Method (ECM). It does not replace a contract, legislation, a controlled standard, competent engineering judgement or specialist advice.

The operating aim is to turn a compact mathematical statement into a usable chain of definitions, claims, examples and checks. Read the original explanation first, then use the workflow and checks below to convert knowledge into evidence.

Treat The Elliptic Curve Method (ECM) as a network of definitions and implications, not as a list of formulas. The working vocabulary on this page—curve, section, elliptic, method, curves—should be made explicit before any proof or computation begins. Record the ambient set or structure, the permitted operations and the equality or equivalence relation in use. A compact theorem often changes meaning when the base field, finiteness condition, commutativity assumption or direction of an action changes.

For a proof, write the hypotheses as a checklist and mark the line at which each one is used. For a computation, state the representation of the input, the arithmetic model, the termination condition and the output invariant. For a classification problem, distinguish existence from uniqueness and distinguish an object from its representation. These separations prevent a correct local calculation from being mistaken for the general result.

A useful worked example should be small enough to inspect completely but rich enough to exercise the main mechanism. Compute the result in two ways where practical: symbolically and by substitution, structurally and numerically, or directly and through a normal form. Then include one near-miss example in which a hypothesis fails. The contrast explains why the theorem is shaped as it is and gives the reader a diagnostic pattern for later problems.

Verification is part of the mathematics. Check domains and codomains, substitute proposed solutions, test identity and zero cases, compare dimensions or cardinalities, and confirm that maps respect the required operations. In numerical work, report precision, conditioning and a residual rather than digits alone. In algorithmic work, separate mathematical correctness from implementation complexity and resource limits.

Step-by-step operating method

Fix the setting. State the objects, ambient structure, notation and assumptions before manipulating symbols.
Separate claims. Distinguish definitions, hypotheses, conclusions, equivalent conditions and consequences.
Choose a method. Select proof, construction, calculation or algorithm according to the question actually asked.
Work a small case. Use the smallest non-trivial example to expose the mechanism and test edge behaviour.
Verify independently. Substitute back, check invariants, test boundary cases or use an alternative derivation.

Worked-example protocol

Illustrative method—not a source theorem. Start with a small admissible input and list the definitions it must satisfy. Carry out each transformation on a separate line, citing the property that permits it. Preserve exact values until approximation is necessary. At the end, verify the output against the original definition and one invariant such as dimension, degree, determinant, order, norm or residual. Then alter one hypothesis and observe which step ceases to be valid. This protocol creates a reusable example without inventing a theorem-specific numerical answer.

Stage	Record	Quality check
Input	Objects, domain, notation, assumptions	Every symbol is defined
Method	Permitted operation or cited result at each step	All hypotheses hold
Output	Exact result and representation	Correct type, domain and form
Verification	Substitution, invariant or alternative derivation	Independent agreement
Boundary test	Zero, identity, degenerate or failed hypothesis	Scope is understood

Common failure modes and recovery actions

1. Watch for

Using a theorem without checking every hypothesis.

Recovery: Return to the governing definition or requirement and restate the decision in one sentence.

2. Watch for

Treating a suggestive example as a proof of the general case.

Recovery: Separate evidence from assumption, assign an owner and set a date for validation.

3. Watch for

Changing notation or conventions part-way through an argument.

Recovery: Run a small counterexample, boundary test, pilot or independent check before proceeding.

4. Watch for

Hiding a division-by-zero, convergence, finiteness or commutativity assumption.

Recovery: Record the consequence, decision and rationale, then update the controlled baseline.

5. Watch for

Reporting a computed result without a residual, substitution or structural check.

Recovery: Escalate when the issue affects safety, compliance, acceptance, material value or an agreed tolerance.

Review checklist

Can every symbol be traced to a definition or prior result?
Which hypothesis does each major step use?
Does the method cover zero, identity, degenerate and boundary cases?
Can the conclusion be checked by a second representation or calculation?
Are mandatory requirements distinguished from recommendations and illustrative values?
Are sources, assumptions, units, dates and versions recorded closely enough to reproduce the decision?
Have safety, legal, ethical, stakeholder and operational consequences been considered at the appropriate level?
Is there a named owner and a trigger for review, escalation, change or retirement?

Questions for deeper application

What is the most important distinction a practitioner must preserve when applying The Elliptic Curve Method (ECM)?