Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 15:38, 1 May 2025

Revision as of 15:42, 1 May 2025

Line 33:

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

We want to factor {{math|1=''n'' = 455839.}} Let's choose the elliptic curve {{math|1=''y''² = ''x''³ + 5''x'' –− 5,}} with the point {{math|1=''P'' = (1, 1)}} on it, and let's try to compute {{math|1=(10!)''P''.}}

The slope of the tangent line at some point ''A''=(''x'', ''y'') is {{math|1=''s'' = (3''x''² + 5)/(2''y'') (mod n)}}. Using ''s'' we can compute 2''A''. If the value of ''s'' is of the form ''a/b'' where ''b'' > 1 and gcd(''a'',''b'') = 1, we have to find the [[modular inverse]] of ''b''. If it does not exist, gcd(''n'',''b'') is a non-trivial factor of ''n''.

First we [[Elliptic_curve_point_multiplication#Point_doubling|compute 2''P'']]. We have {{math|1=''s''(''P'') = ''s''(1,1) = 4,}} so the coordinates of {{math|1=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−53,}} all numbers understood {{math|1=(mod ''n'').}} Just to check that this 2''P'' is indeed on the curve: {{nowrap|1=(–53−53)² = 2809 = 14³ + 5·14 –− 5.}}

Then we compute 3(2''P''). We have {{math|1=''s''(2''P'') = ''s''(14,-53 −53) = –593−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−593/106 = –133317−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>.

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.}}