Lenstra elliptic curve factorization

Lenstra elliptic curve factorization

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 ECM is classified as a deterministic algorithm as all "random" steps (such as the choice of curves) used can be derandomized (using pseudo-random sources) 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, ECM is the third-fastest known factoring method. The second fastest is the multiple polynomial quadratic sieve and the fastest is the general number field sieve; both are probabilistic algorithms, in the sense there is no guarantee that they will return a non trivial factor in the expected running time; there is an exponentially small probability they will take an exponential amount of time.

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 divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor "p" rather than by the size of the number "n" to be factored. Frequently, ECM is used to remove small factors from a very large integer with many factors; if the remaining integer is still composite, then it has only large factors and is factored using general purpose techniques. The largest factor found using ECM so far was discovered on August 24, 2006 by B. Dodson and has 67 digits [http://www.loria.fr/~zimmerma/records/top50.html] . Increasing the number of curves tested improves the chances of finding a factor, but they are not linear with the increase in the number of digits.

Lenstra's elliptic curve factorization

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

* Pick a random elliptic curve over mathbf{Z}/nmathbf{Z}, given by an equation of the form "y"2 = "x"3 + "ax" + "b", and a non-trivial point "A" on it. The group law on this curve is given by rational functions; divisions of residue classes modulo "n" can be performed using the Euclidean algorithm. If in the remaining part of the algorithm a non-zero element of mathbf{Z}/nmathbf{Z} is encountered which fails to be invertible, we get in effect a factorization of "n".

* Compute "eA" in the group of (mathbf{Z}/nmathbf{Z})-valued points of the elliptic curve, where "e" is product of small primes raised to small powers, as in the "p" − 1 algorithm. This 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 two prime divisors "p" and "q" of "n" — as in the "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 "x"-coordinate of "eA" and "n", since this coordinate will be zero in Z"p".

* If it does not work, we can try again with some other curve and starting point.

The complexity depends on the size of the factor and can be represented by O(e(1 + o(1)) √(ln "p" ln ln "p")), where "p" is the smallest factor of "n".

Derivation

ECM is at its core an improvement of the older "p" − 1 algorithm. The "p" − 1 algorithm finds prime factors "p" such that "p" − 1 is b-powersmooth for small values of "b". For any "e", a multiple of "p" − 1, and any "a" relatively prime to "p", by Fermat's little theorem we have "a""e" ≡ "1" (mod "p"). Then gcd("a""e" − 1, "n") is likely to produce a factor of "n". However, the algorithm fails when "p"-1 has large prime factors, as is the case for numbers containing strong primes, for example.

ECM 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 (randomly) between "p" + 1 − 2√"p" and "p" + 1 + 2√"p" by Hasse's theorem, 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 L [√2 / 2, √2] curves before getting a smooth group order. This heuristic estimate is very reliable in practice.

ee also

*UBASIC for practical program (ECMX).
* [http://www.komite.net/laurent/soft/ecm/ecm-6.0.1.html GMP-ECM] , an efficient implementation of ECM.
* [http://www.loria.fr/~zimmerma/records/ecmnet.html ECMNet] , an easy client-server implementation that works with several factorization projects.
* [http://www.sourceforge.net/projects/pyecm pyecm] , a python implementation of ECM. Much faster with psyco and/or gmpy.

Other external links

* [http://alpertron.com.ar/ECM.htm 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 0-387-94777-9

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

* cite journal
last=Pomerance
first=Carl
title=A Tale of Two Sieves
journal=Notices of the American Mathematical Society
pages=1473–1485
volume=43
date=1996
issue=12
url=http://www.ams.org/notices/199612/pomerance.pdf
format = PDF

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… …   Wikipedia

  • Elliptic curve — In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O . An elliptic curve is in fact an abelian variety mdash; that is, it has a multiplication defined algebraically with… …   Wikipedia

  • Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia

  • Hendrik Lenstra — in Berkeley Hendrik Willem Lenstra Junior (* 16. April 1949 in Zaandam, Niederlande) ist ein niederländischer Mathematiker, der sich mit Zahlentheorie beschäftigt. Lenstra wurde 1977 an der Universität Amsterdam bei Frans Oort promoviert mit… …   Deutsch Wikipedia

  • Hendrik Lenstra — Hendrik Willem Lenstra, Jr. (born 1949 in the Netherlands) is a Dutch mathematician. Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978. In 1987 he was appointed to the faculty of the… …   Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • UBASIC — is a freeware BASIC interpreter written by Yuji Kida at Rikkyo University in Japan, specialized on mathematical computing. UBASIC features and discussionUBASIC is a ready to run language that does not need to be set up with some other advanced… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”