Lenstra ECM

Purpose: Factor an integer using elliptic curves. Its running time depends on the size of the smallest prime factor, not on $n$ itself — which makes it the best method for pulling medium-sized factors (up to ~60-70 digits) out of very large numbers.

From Pollard’s $p-1$ to elliptic curves

Pollard’s $p-1$ method: if $p-1$ is $B$-smooth, then for $k=\mathrm{lcm}(\mathrm{1..}B)$ we have $a^k\equiv 1(\mathrm{mod}p)$ by Fermat, so $\gcd (a^k-1,n)$ reveals $p$. The fatal weakness: it only works when that particular $p-1$ happens to be smooth, and you cannot change $p$.

Lenstra’s insight: replace the group ${\mathbb{Z}}_p^{\ast }$ (order $p-1$, fixed) with the group of points on an elliptic curve mod $p$ (order in $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ by Hasse’s theorem, and different for every curve). Now if one curve’s order is not smooth, you simply try another. You get unlimited retries.

Algorithm

1. Pick a random curve $E:y^2=x^3+ax+b(\mathrm{mod}n)$ and a random point $P$ on it. (Trick: pick $x,y,a$ at random and define $b=y^2-x^3-ax$, so $P=(x,y)$ is on the curve by construction.)
2. Compute $kP$ on $E$ modulo $n$, where $k=\mathrm{lcm}(1,\dots ,B_1)$, using repeated point addition.
3. Point addition requires inverting a denominator mod $n$. If that inversion fails, the gcd computed during the extended Euclid gives a non-trivial factor of $n$ — that failure is the success condition.
4. If no failure occurs, pick a new curve and repeat. Optionally add a stage 2 that handles one additional prime factor between $B_1$ and a larger $B_2$.

Complexity

$L_p\left[\frac{1}{2},\sqrt{2}\right]=\exp \left((\sqrt{2}+o(1))\sqrt{\ln p\ln \ln p}\right)$

where $p$ is the smallest prime factor — plus $O({\log }^{2}n)$ per curve operation.

Suggested $B_1$ by factor size

Digits of the factor	$B_1$	Curves needed
15	2 000	~25
20	11 000	~90
30	250 000	~700
40	3 000 000	~2 400
50	44 000 000	~7 500

Why the failure is the point

Working “mod $n$” on a curve is not really a group — it is a group modulo each prime factor simultaneously. When $kP\equiv \mathcal{O}$ (the identity) modulo $p$ but not modulo another prime factor $q$, the addition formula tries to invert something divisible by $p$ but not by $n$. The extended Euclid inside modinv then hands you $\gcd (\cdot ,n)=p$. This happens exactly when the curve’s order modulo $p$ is $B_1$-smooth — and since curve orders vary, enough tries will find one.

Variants / Use Cases

• Montgomery curves and the ladder — the standard implementation; avoids inversions in the inner loop entirely
• Stage 2 (continuation) — catches factors whose order is smooth except for one larger prime; roughly doubles effectiveness for the same cost
• Pollard’s rho — better for small factors (< 20 digits); simpler, no curve arithmetic
• Quadratic Sieve / GNFS — better when $n$ is a semiprime with two equally large factors, which ECM handles poorly
• Integer Factorization — the topic page and the strategy for combining these methods