View source for Elliptic Curve Method

The '''Elliptic Curve Method''' (ECM) is a factorization algorithm that exploits the algebraic structure of [[Elliptic Curves|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 Number|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.''

[[Category:Mathematics]]
[[Category:Cryptography]]