Lenstra elliptic curve factorization

From Free net encyclopedia

The Lenstra elliptic curve factorization or the elliptic curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization which employs elliptic curves. Technically the Lenstra elliptic curve factorization like Pollard's p-1 algorithm is classified as a deterministic algorithm as all "random steps" such as the choice of curves used can be derandomized and done in a deterministic way. (This is not to say that the algorithm can't be implemented in a probabilistic way, if one so chooses, provided one has a true source of randomness.)

For general purpose factoring (on a general purpose computer) this method is the third-fastest factoring method. The second fastest is the multiple polynomial version of the quadratic sieve. The fastest general purpose factoring algorithm is the general number field sieve. Both the quadratic sieve and the general number field sieve are probabilistic algorithms.

Practically speaking, ECM is considered a special purpose factoring algorithm as it is most suitable for finding small factors. Currently, it is still the best algorithm for factoring out divisors of size not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of a factor p rather than by 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 are not linear with the increase in the number of digits.

ECM is at its core an improvement of the older Pollard's p-1 algorithm. In that method, it is 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 numbers). Then, by Fermat's little theorem,

<math>a^e\equiv 1\pmod{p}</math>

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 an elliptic curve over Z_p varies between

<math>p + 1 - 2\sqrt{p}</math>

and

<math>p + 1 + 2\sqrt{p}</math>

by a theorem by Helmut Hasse, and randomly, and is likely to be smooth for some elliptic curves. Although there is no proof that a smooth group order will be found in the Hasse-interval, by using heuristic probabilistic methods, the Canfield-Erdös-Pomerance theorem with suitably optimized parameter choices, and the L-notation, we can expect to try

<math>L_p[\sqrt{2}/2,\sqrt{2}]</math>

curves before getting a smooth group order. This heuristic estimate is very reliable in practice.

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 is tantamount 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).
• GMP-ECM, an efficient implementation of ECM based on the GNU Multi-Precision Library.

Other external links

• Factoring applet that uses ECM

References

• Brent, Richard P. "Factorization of the tenth Fermat number." Mathematics of Computation 68 (1999), 429-451.

• Cohen, Henri. A Course in Computational Algebraic Number Theory. Springer-Verlag, New York, Berlin, Heidelberg, 1996. ISBN 0-387-55640-0.

• Lenstra, A. K. and Lenstra Jr., H. W. (editors), The development of the number field sieve. Lecture Notes in Mathematics 1554, Springer-Verlag, Berlin, 1993. MR 96m:11116.

• Lenstra Jr., H. W. "Factoring integers with elliptic curves." Annals of Mathematics (2) 126 (1987), 649-673. MR 89g:11125.

• {{cite book

   | last = Pomerance
   | first = Carl
   | authorlink = Carl Pomerance
   | coauthors = Richard Crandall
   | year = 2001 
   | title = Prime Numbers: A Computational Perspective 
   | publisher = Springer 
   | edition = 1st edition 
   | chapter = Section 7.4: Elliptic curve method
   | pages = 301–313
   | id = ISBN 0387947779}}

• Pomerance, Carl. "The quadratic sieve factoring algorithm." Advances in Cryptology, Proc. Eurocrypt '84, Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, Berlin, 1985, 169-182. MR 87d:11098.

• Pomerance, Carl. "A Tale of Two Sieves." Notices of the American Mathematical Society 43 (1996), 1473-1485.

• Silverman, Robert D. "The Multiple Polynomial Quadratic Sieve." Mathematics of Computation 48 (1987), 329-339.

fr:Factorisation en courbe elliptique de Lenstra