Lenstra elliptic curve factorization

The Lenstra elliptic curve factorization is a fast probabilistic algorithm for integer factorization which employs elliptic curves.

This method was the best algorithm for integer factorization until the general number field sieve was developed. It is still best for factoring out divisors of size not exceeding 20 digits (64 bits), as its running time depends on the size of a factor p rather than on the size of the number n to be factored.

It is an improvement of the older Pollard p −1 factorization method. In that method, it was assumed that the given number n has a prime factor p such that p-1 had only "small" prime factors (numbers whose prime factors are all "small" are informally called smooth). Then, by Fermat's little theorem, a^e'\'=1 mod p whenever p-1 divides e and p does not divide a. Taking e to be a product of small primes raised to small powers, and a to be a random residue mod n, we can hopefully factor n by computing the greatest common divisor of n and a^e-1, as other divisors q of n are unlikely to have the property that q-1 divides e - smooth values are rare. However, we will not be able to factor n if n does not have a prime factor p with p''-1 smooth.

The Lenstra elliptic curve factorization gets around this obstacle by considering the group of a random elliptic curve over the finite field Z_p, rather than considering the multiplicative group of Z_p which always has order p-1. The order of the group of a random elliptic curve over Z_p varies between p and 2p randomly, and is likely to be smooth for some Elliptic curves.

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

• Pick a random elliptic curve over Z with a point A on it. Then, we consider the group law on this curve mod n - this is possible since almost all residues mod n have inverses, which can be found using the Euclidean algorithm and finding a noninvertible residue tantamounts to factoring n

• Compute eA in this group, where e is product of small primes raised to small powers, as in the Pollard p−1 factorization. It can be done one prime at a time, thus efficiently.

• Hopefully, eA is a zero element of the Elliptic curve group in Z _p, but not in Z _q for another prime divisor q of n (as in the Pollard p−1 method, it is unlikely that both groups will have an order which is a divisor of e). Then we can find a factor of n by finding the greatest common divisor of the first coordinate of A and n, since this coordinate will be zero in Z _p.

• If it does not work, we try with some other curve and starting point

Average and worst case runtime? When was the method developed?