= 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$.<Factoring integers with elliptic curves by Hendrik W. Lenstra, Jr.>[1987, abstract and algorithm description]{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$.
Back to article page
