Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 05:45, 21 July 2025

Latest revision as of 17:59, 17 August 2025

(One intermediate revision by one other user not shown)

Line 9:

The Lenstra elliptic-curve factorization method to find a factor of a given natural number <math>n</math> works as follows:

# Pick a random [[elliptic curve]] over <math>\mathbb{Z}/n\mathbb{Z}</math> (the integers modulo <math>n</math>), with equation of the form <math>y^2 = x^3 + ax + b \pmod n</math> together with a non-trivial [[Point (geometry)|point]] <math>P(x_0,y_0)</math> on it.

#:This can be done by first picking random <math>x_0,y_0,a \in \mathbb{Z}/n\mathbb{Z}</math>, and then setting <math>b = y_0^2 - x_0^3 - ax_0\pmod n</math> to assureensure the point is on the curve.

# One can define ''Addition'' of two points on the curve, to define a [[Group (mathematics)|group]]. The addition laws are given in the [[elliptic curve#The group law|article on elliptic curves]].

#:We can form repeated multiples of a point <math>P</math>: <math>[k]P = P + \ldots + P \text{ (k times)}</math>. The addition formulae involve taking the modular slope of a chord joining <math>P</math> and <math>Q</math>, and thus division between residue classes modulo <math>n</math>, performed using the [[extended Euclidean algorithm]]. In particular, division by some <math>v \bmod n</math> includes calculation of the <math>\gcd(v,n)</math>.

Line 183:

* [http://ecm.gforge.inria.fr/ GMP-ECM] {{Webarchive|url=https://web.archive.org/web/20090912000929/http://ecm.gforge.inria.fr/ |date=2009-09-12 }}, an efficient implementation of ECM.

* [http://www.loria.fr/~zimmerma/records/ecmnet.html ECMNet], an easy client-server implementation that works with several factorization projects.

* [httphttps://www.sourceforge.net/projects/pyecm pyecm], a python implementation of ECM.

* [http://www.rechenkraft.net/yoyo/ Distributed computing project yoyo@Home] Subproject ECM is a program for Elliptic Curve Factorization which is used to find factors for different kinds of numbers.

* [https://web.archive.org/web/20130811025532/http://ardoino.com/2008/03/large-integers-factorization/ Lenstra Elliptic Curve Factorization algorithm source code] Simple C and GMP Elliptic Curve Factorization Algorithm source code.