Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 05:56, 22 March 2024

Revision as of 23:04, 16 April 2024

Line 37:

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'' = (''x′{{prime|x}}'', ''y′{{prime|y}}'')}} are {{math|1=''x′{{prime|x}}'' = ''s''² – 2''x'' = 14}} and {{math|1=''y′{{prime|y}}'' = ''s''(''x'' – ''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.}}

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

Line 47:

==The algorithm with projective coordinates==

Before considering the projective plane over <math>(\Z/n\Z)/\sim,</math> first consider a 'normal' [[projective space]] over ℝ<math>\mathbb{R}</math>: Instead of points, lines through the origin are studied. A line may be represented as a non-zero point <math>(x,y,z)</math>, under an equivalence relation ~ given by: <math>(x,y,z)\sim(x',y',z')</math> ⇔ ∃ '''''c''''' ≠ 0 such that ''x' = '''c'''x'', ''y' = '''c'''y'' and ''z' = '''c'''z''. Under this equivalence relation, the space is called '''the projective plane''' <math>\mathbb{P}^2</math>; points, denoted by <math>(x:y:z)</math>, correspond to lines in a three-dimensional space that pass through the origin. Note that the point <math>(0:0:0)</math> does not exist in this space since to draw a line in any possible direction requires at least one of x',y' or z' ≠ 0. Now observe that almost all lines go through any given reference plane - such as the (''X'',''Y'',1)-plane, whilst the lines precisely parallel to this plane, having coordinates (''X,Y'',0), specify directions uniquely, as 'points at infinity' that are used in the affine (''X,Y'')-plane it lies above.

In the algorithm, only the group structure of an elliptic curve over the field ℝ<math>\mathbb{R}</math> is used. Since we do not necessarily need the field ℝ<math>\mathbb{R}</math>, a finite field will also provide a group structure on an elliptic curve. However, considering the same curve and operation over <math>(\Z/n\Z)/\sim</math> with {{mvar|n}} not a prime does not give a group. The Elliptic Curve Method makes use of the failure cases of the addition law.

We now state the algorithm in projective coordinates. The neutral element is then given by the point at infinity <math>(0:1:0)</math>. Let {{mvar|n}} be a (positive) integer and consider the elliptic curve (a set of points with some structure on it) <math>E(\Z/n\Z)=\{(x:y:z) \in \mathbb{P}^2\ |\ y^2z=x^3+axz^2+bz^3\}</math>.