Lenstra elliptic-curve factorization: Difference between revisions

Revision as of 18:34, 19 October 2022

Revision as of 20:38, 19 October 2022

Line 12:

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

#*If we finish all the calculations above without encountering non-invertible elements (<math>\bmod n</math>), it means that the elliptic curves' (modulo primes) order is not [[Smooth number|smooth]] enough, so we need to try again with a different curve and starting point.

#*If we encounter a <math>\gcd(v,n) \neq 1,n</math> we are done;: we haveit foundis a non-trivial factor of <math>n</math>.

The time complexity depends on the size of the number's smallest prime factor and can be represented by {{math|1=exp[({{sqrt|2}}&nbsp;+&nbsp;[[Big O notation#Little-o notation|o]](1)) {{sqrt|ln&nbsp;''p''&nbsp;ln&nbsp;ln&nbsp;''p''}}]}}, where ''p'' is the smallest factor of ''n'', or <math>L_p\left[\frac{1}{2},\sqrt{2}\right]</math>, in [[L-notation]].