Elliptic-curve factorization method

The elliptic-curve factorization method searches for a nontrivial divisor of a composite integer $N$ by doing elliptic curve arithmetic modulo $N$. Hendrik W. Lenstra's method replaces the multiplicative group in Pollard's p-1 algorithm with a group whose order varies as the curve varies. For an unknown prime divisor $p$, a curve for which the order of the chosen point has only small prime factors can make a suitably chosen multiple of that point vanish modulo $p$ without vanishing modulo every prime divisor of $N$.^[ref]

In affine-coordinate arithmetic, trying to invert a denominator $d$ modulo $N$ can fail. Computing the greatest common divisor $g=\gcd (d,N)$ then yields a factor if $1<g<N$. A full gcd of $N$ is inconclusive; another curve or point may be needed. Implementations can accumulate this information with projective coordinates rather than attempting an inversion at every step.

For a small worked example, take $N=35$, the curve $y^2=x^3+x+1$, and $P=(0,1)$. Its discriminant $-16(4+27)$ is coprime to $35$. The usual addition formulas give $2P=(9,12)$ and $3P=(2,16)$ modulo $35$. Adding these to form $5P$ calls for inversion of $9-2=7$. Since $\gcd (7,35)=7$, the failed division exposes a prime divisor. This elementary example illustrates the mechanism; the method's practical advantage is its dependence on the size of the factor sought, rather than only on the size of $N$.