Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 00:55, 25 December 2024

Latest revision as of 17:59, 17 August 2025

(4 intermediate revisions by 3 users 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 23:

If ''p'' and ''q'' are two prime divisors of ''n'', then {{math|1=''y''²&nbsp;=&nbsp;''x''³&nbsp;+}} {{math|1=''ax''&nbsp;+&nbsp;''b''&nbsp;(mod&nbsp;''n'')}} implies the same equation also {{math|1=modulo&nbsp;''p''}} and {{math|1=modulo&nbsp;''q''.}} These two smaller elliptic curves with the <math>\boxplus</math>-addition are now genuine [[group (mathematics)|groups]]. If these groups have ''N''_''p'' and ''N_q'' elements, respectively, then for any point ''P'' on the original curve, by [[Lagrange's theorem (group theory)|Lagrange's theorem]], {{math|1=''k''&nbsp;>&nbsp;0}} is minimal such that <math>kP=\infty</math> on the curve modulo ''p'' implies that ''k'' divides ''N''_''p''; moreover, <math>N_p P=\infty</math>. The analogous statement holds for the curve modulo ''q''. When the elliptic curve is chosen randomly, then ''N''_''p'' and ''N''_''q'' are random numbers close to {{math|1=''p''&nbsp;+&nbsp;1}} and {{math|1=''q''&nbsp;+&nbsp;1,}} respectively (see below). Hence it is unlikely that most of the prime factors of ''N''_''p'' and ''N''_''q'' are the same, and it is quite likely that while computing ''eP'', we will encounter some ''kP'' that is &infin; {{math|1=modulo&nbsp;''p''}} but not {{math|1=modulo&nbsp;''q'',}} or vice versa. When this is the case, ''kP'' does not exist on the original curve, and in the computations we found some ''v'' with either {{math|1=gcd(''v'',''p'')&nbsp;=&nbsp;''p''}} or {{math|1=gcd(''v'',&nbsp;''q'')&nbsp;=&nbsp;''q'',}} but not both. That is, {{math|1=gcd(''v'',&nbsp;''n'')}} gave a non-trivial factor {{math|1=of&nbsp;''n''.}}

ECM is at its core an improvement of the older [[Pollard's p &minus; 1 algorithm|{{math|1=''p''&nbsp;&minus;&nbsp;1}} algorithm]]. The {{math|1=''p''&nbsp;&minus;&nbsp;1}} algorithm finds prime factors ''p'' such that {{math|1=''p''&nbsp;&minus;&nbsp;1}} is [[smooth number|b-powersmooth]] for small values of ''b''. For any ''e'', a multiple of {{math|1=''p''&nbsp;&minus;&nbsp;1,}} and any ''a'' [[relatively prime]] to ''p'', by [[Fermat's little theorem]] we have {{math|1=''a''^''e''&nbsp;&equiv;&nbsp;1 ([[modular arithmetic|mod]] ''p'')}}. Then {{math|1=[[greatest common divisor|gcd]](''a''^''e''&nbsp;&minus;&nbsp;1,&nbsp;''n'')}} is likely to produce a factor of ''n''. However, the algorithm fails when {{math|1=''p''&nbsp;-−&nbsp;1}} has large prime factors, as is the case for numbers containing [[strong prime]]s, for example.

ECM gets around this obstacle by considering the [[group (mathematics)|group]] of a random [[elliptic curve]] over the [[finite field]] '''Z'''_''p'', rather than considering the [[multiplicative group]] of '''Z'''_''p'' which always has order&nbsp;{{math|1=''p''&nbsp;&minus;&nbsp;1.}}

Line 33:

The following example is from {{harvtxt|Trappe|Washington|2006}}, with some details added.

We want to factor {{<math|1=''>n'' = 455839</math>.}} Let's choose the elliptic curve {{<math|1=''>y''^{^2} = ''x''^{^3} + 5''x''5x –- 5</math>,}} with the point {{<math|1=''>P'' = (1, 1)}}</math> on it, and let's try to compute {{the point <math|1=>(10!)''P''</math>.}}

The slope of the tangent line at some point ''<math>A''=(''x'', ''y'')</math> ison {{math|1=''s''the =curve is (3''x''<supmath>\lambda=\frac{3x^2</sup> + 5)/(2''y'')}{2y}\ (\mathrm{mod}\ n)}}</math>. Using ''s''<math>\lambda</math>, we can compute 2''A''point <math>2A</math>. If the value of ''s''<math>\lambda</math> isdoes ofnot theexist, formas ''a/b'' whereresult ''b''of <math>y</math> 1not andhaving gcd(''a'',''b'') = 1, we have to find the [[modular inverse]], of ''b''. If it does not exist,then <math>\gcd(''n'',''b''y)</math> is a non-trivial factor of ''<math>n''</math>.

First, we compute <math>2!P</math>. Using [[Elliptic_curve_point_multiplication#Point_doubling|computepoint 2''P''doubling]]., Wewe have {{<math|1=''s''>\lambda(''P'') = ''s''\lambda(1,1) = 4</math>,}} so the coordinates of {{point <math|1>2P=2''P'' = (''{{prime|x}}'', ''{{prime|y}}'')}} are {{math|1=''{{prime|x}}'' = ''s''² – 2''x'' = 14}} and {{math|1=''{{prime|y}}'' = ''s''(''x'' – ''{{prime|x}}'') – ''y''}} {{math|1== 4(1 – 14) – 1 = –53,}} all numbers understood {{math|1=(mod ''n'').}} Just to check that this 2''P'' is indeed on the curve: {{nowrap|1=(–53)² = 2809 = 14³ + 5·14 – 5.}}are

:<math>x'=4^2-2(1)=14</math>

:<math>y'=4(1-14)-1=-53</math>

yielding the point <math>2P=(14,-53)</math>.

Next, we compute <math>3!P</math>. We have <math>\lambda(2P)=\lambda(14,-53)=-593/106\ (\mathrm{mod}\ n)</math>. Since <math>\gcd(106,455839)=1</math>, the modular inverse of 106 exists. Using the [[extended Euclidean algorithm]], we can obtain that <math>\lambda=-593/106=322522\ (\mathrm{mod}\ 455839)</math>.

Then we compute 3(2''P''). We have {{math|1=''s''(2''P'') = ''s''(14,-53) = –593/106 (mod ''n'').}} Using the [[Euclidean algorithm]]: {{nowrap|1=455839 = 4300·106 + 39,}} then {{nowrap |1=106 = 2·39 + 28,}} then {{nowrap|1=39 = 28 + 11,}} then {{nowrap |1=28 = 2·11 + 6,}} then {{nowrap|1=11 = 6 + 5,}} then {{nowrap |1=6 = 5 + 1.}} Hence {{nowrap|1=gcd(455839, 106) = 1,}} and working backwards (a version of the [[extended Euclidean algorithm]]): {{nowrap |1=1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11}} {{nowrap |1== 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839.}} Hence {{nowrap |1=106⁻¹ = 81707 (mod 455839),}} and {{nowrap |1=–593/106 = –133317 (mod 455839).}} Given this ''s'', we can compute the coordinates of 2(2''P''), just as we did above: {{math|1=4''P'' = (259851, 116255).}} Just to check that this is indeed a point on the curve: {{math|1=''y''² = 54514 = ''x''³ + 5''x'' – 5 (mod 455839).}} After this, we can compute <math>3(2P) = 4P \boxplus 2P</math>.

Given this, we can compute the coordinates of <math>2(2P)</math>, just as we did above. The coordinates of point <math>4P=(x',y')</math> are

We can similarly compute 4!''P'', and so on, but 8!''P'' requires inverting {{nowrap|1=599 (mod 455839).}} The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a {{nowrap|1=factorization 455839 = 599·761.}}

:<math>x'=322522^2-2(14)=259851\pmod{455839}</math>

:<math>y'=322522(14-259851)-(-53)=116255\pmod{455839}</math>

This yields <math>4P=(259851,116255)</math>.

After this, we can compute <math>3(2P) = 4P + 2P</math> using [[Elliptic_curve_point_multiplication#Point_addition|point addition]]. The line joining <math>4P</math> and <math>2P</math> has slope <math>\lambda=116308/259837=206097\ (\mathrm{mod}\ n)</math>, so the coordinates of <math>6P=(x',y')</math> are

The reason that this worked is that the curve {{nowrap|1=(mod 599)}} has {{nowrap|1=640 = 2⁷·5}} points, while {{nowrap|1=(mod 761)}} it has {{nowrap|1=777 = 3·7·37}} points. Moreover, 640 and 777 are the smallest positive integers ''k'' such that {{math|1=''kP'' = &infin;}} on the curve {{nowrap|1=(mod 599)}} and {{math|1=(mod 761),}} respectively. Since {{nowrap|8!}} is a multiple of 640 but not a multiple of 777, we have {{math|1=8!''P'' = &infin;}} on the curve {{nowrap|1=(mod 599),}} but not on the curve {{nowrap|1=(mod 761),}} hence the repeated addition broke down here, yielding the factorization.

:<math>x'=206097^2-14-259851=179685\pmod{455839}</math>

:<math>y'=206097(14-179685)-(-53)=427131\pmod{455839}</math>

yielding the point <math>6P=(179685,427131)</math>

We can similarly compute points <math>4!''P''</math>, <math>5!P</math>, and so on, but computing <math>8!''P''</math> requires inverting {{nowrap|1=599 (mod 455839).}}, Thewhich Euclideanis algorithmnot givespossible thatbecause <math>\gcd(599,455839)\ne1</math>. is divisible by 599Thus, and we have found a factorization {{nowrap|1=factorization 455839 = 599·761.}}.

The reason that this workedworks is that the curve {{nowrap|1=(mod 599)}} has {{nowrap|1=640 = 2⁷·5}} points, while {{nowrap|1=(mod 761)}} it has {{nowrap|1=777 = 3·7·37}} points. Moreover, 640 and 777 are the smallest positive integers ''k'' such that {{math|1=''kP'' = &infin;}} on the curve {{nowrap|1=(mod 599)}} and {{mathnowrap|1=(mod 761),}} respectively. Since {{nowrap|8!}} is a multiple of 640 but not a multiple of 777, we have {{math|1=8!''P'' = &infin;}} on the curve {{nowrap|1=(mod 599),}} but not on the curve {{nowrap|1=(mod 761),}} hence the repeated addition broke down here, yielding the factorization.

==The algorithm with projective coordinates==

Line 170 ⟶ 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.