Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 17:43, 2 May 2018

Revision as of 07:30, 8 May 2018

Line 31:

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 compute 2''P''. We have {{math|1=''s''(''P'')  =  ''s''(1,1)  =  4,}} so the coordinates of {{math|1=2''P''  =  (''x′'',  ''y′'')}} are {{nowrapmath|1=''x′'' = ''s''² – 2''x'' = 14}} and {{nowrapmath|1=''y′'' = ''s''(''x'' – ''x′'') – ''y''}} {{math|1==  4(1  –  14)  –  1  =  –53,}} all numbers {{math|1=understood  (mod  ''n'').}} Just to check that this 2''P'' is indeed on the curve: {{mathnowrap|1=(–53)²  =  2809  =  14³  +  5·14  –  5.}}

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

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

==The algorithm with projective coordinates==