Lenstra’s elliptic-curve method factors an integer by doing arithmetic that would be perfectly legal modulo a prime factor—but can fail modulo the whole composite.
The failure is useful. When an elliptic-curve addition formula asks us to invert a denominator that is invertible modulo one prime factor of n but not another, the greatest common divisor of that denominator with n can reveal a nontrivial factor.
ECM is especially important when the smallest unknown prime factor is much smaller than the composite number itself. Its expected work depends strongly on the size of that factor rather than only on the size of n. This makes it a natural companion to Pollard p−1 and a practical preprocessing stage before methods aimed at equally sized large factors.
This is Guide 21 in the Bukit Timah Tutor Computational Number Theory series. It deepens the factorisation overview in Guide 4 and uses elliptic-curve arithmetic from Guide 8. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. From Pollard p−1 to ECM
Pollard p−1 hopes that, for an unknown prime factor p of n, the group order p−1 is smooth: built only from small prime powers. If so, a large exponent M divisible by those prime powers can force an element into the identity modulo p.
ECM changes the group. Instead of using the fixed multiplicative group modulo p, it chooses a random elliptic curve E and works in E(F_p). The group order #E(F_p) varies with the curve.
This randomness is the key advantage. Even if p−1 has a large prime factor, some elliptic curve modulo p may have a smooth group order. Trying another curve changes the group without changing the hidden factor p.
2. Arithmetic modulo a composite is only partially field-like
Over a prime field, a nonzero denominator always has an inverse. Over Z/nZ with composite n, a nonzero residue may share a factor with n and fail to invert.
Suppose n=pq with unknown p and q. A denominator d may be zero modulo p but nonzero modulo q. Then gcd(d,n)=p.
ECM deliberately performs elliptic-curve arithmetic modulo n until such a noninvertible denominator appears. The arithmetic before failure behaves consistently modulo every prime factor of n.
3. Choose a curve and point
Take a short Weierstrass equation
E: y² = x³+Ax+B (mod n)
with a point P=(x,y) satisfying the equation modulo n. The discriminant expression 4A³+27B² should be coprime to n. If its gcd with n is already nontrivial, a factor has been found before scalar multiplication begins.
In practical ECM implementations, curve parameterisations such as Montgomery curves are chosen for faster scalar multiplication and convenient batch arithmetic. The underlying factorisation principle is the same.
4. A complete toy factorisation of 91
Let n=91=7·13, but pretend the factors are unknown. Use
E: y² = x³+48 (mod 91) P=(1,7).
Check the point:
7² = 49, 1³+48 = 49 (mod91).
The discriminant factor 27·48² is coprime to 91, so the curve itself does not immediately expose a factor.
Now try to double P. The tangent formula requires inversion of 2y=14 modulo 91. But
gcd(14,91)=7.
We have found a nontrivial factor without completing the doubling. The complementary factor is 91/7=13.
This toy example makes the mechanism visible. Real ECM normally performs many legal additions before a denominator failure occurs.
5. Why a denominator failure means different behaviour modulo factors
Reduce the computation separately modulo 7 and modulo 13. Modulo 7, the y-coordinate of P is zero, so doubling reaches a vertical tangent situation. Modulo 13, y=7 is nonzero and the denominator 14≡1 is invertible.
The single computation modulo 91 is trying to serve both component fields at once. The attempted inverse exists in one component and not the other. The gcd recovers exactly the component where inversion failed.
This is an instance of the Chinese Remainder Theorem operating behind the scenes: Z/91Z decomposes into arithmetic modulo 7 and modulo 13.
6. Stage one: build a smooth exponent
Choose a smoothness bound B1. Construct
M = product over primes l≤B1 of l^floor(log_l B1).
Equivalently, M is the least common multiple of 1,2,…,B1.
Compute Q=[M]P on the chosen elliptic curve modulo n. If an unknown prime factor p has the property that the order of P in E(F_p) divides M, then Q becomes the identity modulo p.
During scalar multiplication, projective coordinates avoid an inversion at every addition. At the end, a projective denominator or Z-coordinate can be tested with gcd against n.
7. The smooth-order success condition
Let r be the order of P modulo an unknown prime factor p. Stage one succeeds when r is B1-smooth enough to divide M.
The entire group order #E(F_p) need not divide M if P happens to lie in a smoother subgroup. Conversely, a smooth group order is sufficient for every point order to be smooth.
The algorithm’s probability analysis therefore concerns the distribution of elliptic-curve group orders and point orders near p.
8. Hasse’s interval makes the randomisation plausible
For prime p, Hasse’s theorem gives
|#E(F_p)−(p+1)| ≤ 2√p.
Different curves produce different orders inside this interval. ECM samples from this family of nearby group sizes.
The method does not require us to know #E(F_p). It relies on the chance that one sampled group order is smooth enough for the chosen bounds.
9. What to do when stage one returns no factor
A failed curve is normal. The point order modulo p may contain a prime factor larger than B1. Increase bounds or choose another curve.
If a gcd equals n rather than a proper factor, too much information may have vanished simultaneously across multiple prime factors. Backtracking through a product tree or using smaller batches can isolate the first nontrivial gcd.
No factor found is not a primality certificate. ECM is a factor search method.
10. Stage two extends the smoothness window
Stage two targets orders that are almost B1-smooth except for one additional prime factor between B1 and a larger bound B2.
Starting from the stage-one point Q, one computes structured multiples corresponding to candidate primes in that interval and accumulates products of coordinate differences or related expressions. A single gcd can test many candidates in a batch.
The exact stage-two formulas vary by curve model and implementation. The conceptual objective is stable: reuse the expensive stage-one work while allowing one moderately larger prime in the point order.
11. Why ECM likes many independent curves
Increasing B1 makes each curve more expensive but raises its chance of success. Trying many curves keeps each attempt cheaper while sampling more group orders.
Good implementations choose B1, B2 and the number of curves according to the expected factor size. These are performance parameters, not mathematical correctness parameters.
The same composite can behave very differently on two curves because #E(F_p) changes.
12. Projective coordinates
Affine point addition requires modular inversion frequently. In ECM, an inversion failure could reveal a factor, but performing a gcd at every addition is expensive.
Projective coordinate systems replace most inversions with multiplications and squarings. One then batches or postpones inversion/gcd work.
Montgomery x-only arithmetic is particularly common because scalar multiplication can be implemented efficiently with differential addition and doubling.
13. The Montgomery ladder viewpoint
A ladder processes scalar bits while maintaining two related multiples, typically [k]P and [k+1]P. Each bit performs one doubling and one differential addition.
For ECM this gives a regular arithmetic pattern and efficient x-coordinate formulas. The purpose here is performance and structural simplicity, not a claim that a classroom pseudocode implementation is production-grade.
14. Batch gcd
If many denominators d_i need testing, multiply them modulo n:
D = d1 d2 … dt mod n.
Then compute gcd(D,n). If the gcd is one, every d_i is invertible modulo every factor. If the gcd is proper, at least one d_i exposes a factor.
If gcd(D,n)=n, use a product tree or divide-and-conquer backtracking to locate a smaller subset responsible for the failure.
This trades many gcd operations for multiplications, which is often advantageous.
15. Complexity depends on the factor, not just n
Lenstra’s original analysis emphasises that ECM is substantially faster when n contains a relatively small prime factor p. Its heuristic expected cost is subexponential in log p, with only polynomial dependence on log n for the modular arithmetic surrounding that search.
This makes ECM different from the quadratic sieve and general number field sieve, whose principal asymptotic scale is tied more directly to n itself.
ECM is therefore often used to remove medium-sized factors before applying a heavier sieve method to the remaining cofactor.
16. ECM versus Pollard p−1
Pollard p−1 is extremely effective when p−1 is smooth. ECM replaces the fixed order p−1 with many random elliptic-curve orders near p.
If p−1 is unfriendly, another elliptic curve may still have a friendly order. The cost is more complicated group arithmetic.
The two methods share the same strategic pattern: force a group element into an identity modulo p while it remains nontrivial modulo another factor, then extract the mismatch with gcd.
17. Verification of a returned factor
A reported divisor d is easy to verify:
1<d<n and n mod d = 0.
No trust in the elliptic-curve search is needed once the factor is printed.
If complete factorisation is required, recursively factor d and n/d and prove terminal factors prime with deterministic or certificate-based methods.
18. Common mistakes
1. Treating arithmetic modulo composite n as a field. 2. Forgetting to gcd the curve discriminant with n. 3. Assuming one failed curve means ECM cannot find the factor. 4. Confusing the full curve order with the chosen point order.
5. Calling a stage-one miss evidence of primality. 6. Ignoring the gcd=n case in batching. 7. Using affine inversions at every step and overlooking their cost. 8. Reporting search complexity only in terms of n when ECM’s advantage is tied to the size of the target factor.
19. Practice set
1. Explain the difference between Pollard p−1 and ECM. 2. For E:y²=x³+48 mod91, verify that P=(1,7) lies on the curve. 3. Compute gcd(2y,91). 4. Explain why this reveals a factor.
5. What is the purpose of B1? 6. What is M=lcm(1,…,B1) trying to absorb? 7. Does stage one require the exact curve order? 8. What does Hasse’s bound say about that order?
9. What does stage two allow beyond stage one? 10. Why are many curves useful? 11. What advantage do projective coordinates provide? 12. What does batch gcd accomplish?
13. Why can gcd(D,n)=n be inconvenient? 14. How is a returned factor independently verified? 15. Why is ECM useful before NFS? 16. Is ECM a primality-proving algorithm?
20. Answers
1. Pollard p−1 uses the fixed multiplicative group of order p−1; ECM samples elliptic-curve groups with varying orders. 2. Both sides equal 49 modulo91. 3. gcd(14,91)=7. 4. The doubling denominator is noninvertible modulo one hidden prime component.
5. It sets the stage-one smoothness bound. 6. Small prime powers in the point order. 7. No. 8. #E(F_p) lies within 2√p of p+1.
9. One additional moderately sized prime factor in the order. 10. Each curve samples a different group order. 11. They replace most inversions with multiplications and squarings. 12. It tests many possible nonunits using one gcd.
13. Several failures may have been multiplied together, so one must backtrack to isolate a proper factor. 14. Check exact divisibility. 15. It can cheaply remove medium-sized factors, leaving a harder balanced cofactor for sieve methods. 16. No.
Sources and further study
Hendrik W. Lenstra Jr., Factoring integers with elliptic curves, Annals of Mathematics 126 (1987), 649–673, is the foundational ECM paper. Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, develops ECM alongside other factoring methods.
Continue through Batch 06
Continue to Guide 22: Quadratic Sieve, Factor Bases, Smooth Relations and Linear Algebra, then Guide 23: Number Field Sieve, Polynomial Selection, Sieving and Square Roots, and Guide 24: ECPP and Verifiable Prime Certificates.