Elliptic Curve Method

The Elliptic Curve Method (ECM) is a factorization algorithm that exploits the algebraic structure of elliptic curves over finite fields to find medium-sized prime factors of composite integers. Invented by Hendrik Lenstra in 1985, ECM is particularly effective at finding factors in the 20–50 digit range, where it outperforms both trial division and the Quadratic Sieve for individual factor extraction. The method relies on the property that the order of an elliptic curve group varies with the curve choice, and when this order is smooth with respect to a chosen bound, the computation reveals a factor through a group operation failure.

ECM is the forgotten workhorse of factorization: not as celebrated as the General Number Field Sieve, but indispensable for stripping small and medium factors before heavy artillery is deployed. Its elegance lies in turning a structural property of elliptic curves — the unpredictability of their group orders — into a randomized search strategy that no deterministic method can match.