Lenstra Elliptic Curve Factorization - Lenstra's Elliptic Curve Factorization

Lenstra's Elliptic Curve Factorization

The Lenstra elliptic curve factorization method to find a factor of the given number n works as follows:

1. Pick a random elliptic curve over, given by an equation of the form y2 = x3 + ax + b (mod n), and a non-trivial point P on it. Say, pick first a point P=(x,y) with random non-zero coordinates x,y (mod n), then pick a random non-zero a (mod n), then take b = y2 - x3 - ax (mod n).
2. We will compute certain multiples (k times) of the point P using the standard addition rule on our elliptic curve: given two points P,Q on the curve, their sum can be computed using the formulas given in the group law section of the article on elliptic curves. These formulas contain the "slope" of the line connecting P and Q, hence involve divisions between residue classes modulo n, which can be performed using the extended Euclidean algorithm. In particular, division by some v (mod n) includes the calculation of the greatest common divisor gcd(v,n).

   If the slope is of the form u/v with gcd(u,n)=1, then v=0 (mod n) means that the result of the -addition will be, the point at infinity on the curve. However, if gcd(v,n) is neither 1 nor n, then the -addition will not produce a meaningful point on the curve, which shows that our elliptic curve is not a group (mod n), but, more importantly for now, gcd(v,n) is a non-trivial factor of n.

3. Compute eP on the elliptic curve (mod n), where e is product of many small numbers: say, a product of small primes raised to small powers, as in the p − 1 algorithm, or the factorial B! for some not too large B. This can be done efficiently, one small factor at a time. Say, to get B!P, first compute 2P, then 3(2P), then 4(3!P), and so on. Of course, B should be small enough so that B-wise -addition can be performed in reasonable time.
4. • If we were able to finish all the calculations above without encountering non-invertible elements (mod n), then we need to try again with some other curve and starting point.
   • If we found at some stage (the point at infinity on the elliptic curve), then again we should start over with a new curve and starting point, since is the zero element for, so after this point we would be just repeating .
   • If we encountered a gcd(v,n) at some stage that was neither 1 nor n, then we are done: it is a non-trivial factor of n.

The time complexity depends on the size of the factor and can be represented by O(e(√2 + o(1)) √(ln p ln ln p)), where p is the smallest factor of n, or, in L-notation.