Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 18:24, 8 October 2019

Revision as of 22:33, 20 December 2019

Line 8:

#: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 assure 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>.

#: Assuming we calculate a slope of the form <math>u/v</math> with <math>\gcd(u,v)=1</math>, then if <math>v = 0 \bmod n</math>, the result of the point addition will be <math>\infty</math>, the point "at infinity" corresponding to the intersection of the "vertical" line joining <math>P(x,y), P'(x,-y)</math> and the curve. However, if <math>\gcd(v,n) \neq 1, n</math>, then the point addition will not produce a meaningful point on the curve; but, more importantly, <math>\gcd(v,n)</math> is a non-trivial factor of <math>n</math>.

# Compute <math>[k]P</math> on the elliptic curve (<math>\bmod n</math>), where <math>k</math> is a product of many small numbers: say, a product of small primes raised to small powers, as in the [[Pollard's p &minus; 1 algorithm|p-1 algorithm]], or the [[factorial]] <math>B!</math> for some not too large <math>B</math>. This can be done efficiently, one small factor at a time. Say, to get <math>[B!]P</math>, first compute <math>[2]P</math>, then <math>[3]([2]P)</math>, then <math>[4]([3!]P)</math>, and so on. <math>B</math> is picked to be small enough so that <math>B</math>-wise point addition can be performed in reasonable time.