Elliptic-curve factorization method 2026-11-05
The elliptic-curve factorization method searches for a nontrivial divisor of a composite integer by doing elliptic curve arithmetic modulo . 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 , 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 without vanishing modulo every prime divisor of .[ref]
In affine-coordinate arithmetic, trying to invert a denominator modulo can fail. Computing the greatest common divisor then yields a factor if . A full gcd of 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 , the curve , and . Its discriminant is coprime to . The usual addition formulas give and modulo . Adding these to form calls for inversion of . Since , 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 .
John Pollard (mathematician) Created 2026-10-31 Updated 2026-11-05
John Pollard is a mathematician whose work in number theory includes Pollard's rho algorithm and Pollard's p-1 algorithm for integer factorization. His retrospective explains how collision ideas related to the birthday paradox lead to the rho method, and distinguishes its factorization and discrete logarithm applications.[ref]
https://sites.google.com/site/jmptidcott2/50-years-of-the-rho-method. Author's retrospective, 50 Years of the rho method
Homepage: sites.google.com/site/jmptidcott2/
In Pollard's p-1 algorithm, a large exponent containing many small factors makes divisible by a prime factor whose predecessor divides , by Fermat's little theorem. A greatest common divisor with the number being factored can then separate that prime factor from the others.
Choose base and build factorial exponents using modular exponentiation. The successive exponents , , and giveThe first two greatest common divisors are . At the next step the Euclidean algorithm givesHenceHere the element order of modulo is , which divides , even though does not divide . The algorithm only needs the element order to divide the chosen exponent; divisibility by the full predecessor is a sufficient condition, not a necessary one.