= Elliptic curve method
{wiki=Lenstra_elliptic-curve_factorization}
Attempt scalar multiplication on an <elliptic curve> modulo a composite <integer>. An addition denominator that is not invertible yields a <greatest common divisor> with the modulus; a value strictly between one and the modulus is a factor. The method exploits different orders of the reduced point at the unknown <prime> factors. For $y^2=x^3+5x-5$ modulo $221$, doubling $(1,1)$ gives $(14,-53)$; adding the original point requires division by thirteen, revealing $221=13\cdot17$.
Back to article page
