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 greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time depends on the size of a factor p rather than on the size of the number n to be factored. The largest factor found (the co-factor being larger) by ECM as of several years ago was around 50 digits. Increasing the number of curves tested improves the chances, but they aren't linear with the increase in the number of digits.
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, ae=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 ae-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 Zp, rather than considering the multiplicative group of Zp which always has order p-1. The order of the group of a random elliptic curve over Zp varies between p+1-2*sqrt(p) and p+1+2*sqrt(p) (a theorem by Helmut Hasse) 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.
See also
- UBASIC for practical program (ECMX).