Introduction to EECM (original) (raw)

ECM, the elliptic-curve method of integer factorization, was introduced in the following paper: Hendrik W. Lenstra, Jr. Factoring integers with elliptic curves. Annals of Mathematics 126 (1987), 649–673. Several refinements to ECM were eventually combined into a standard implementation, GMP-ECM, written by a team led by Paul Zimmermann. See http://ecm.gforge.inria.fr.

A new addition formula for curves of the form x^2+y^2=1+dx^2y^2 was introduced in the following paper, generalizing from one curve studied by Euler and Gauss:

• Harold M. Edwards. A normal form for elliptic curves. Bulletin of the American Mathematical Society 44 (July 2007), 393–422. URL:http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html.

Initial analysis and optimization of Edwards-curve operation counts by Daniel J. Bernstein and Tanja Lange suggested that Edwards curves would save time in many elliptic-curve computations, including ECM. See https://hyperelliptic.org/tanja/newelliptic/.

GMP-EECM, a variant of GMP-ECM, was the first software to set speed records using Edwards curves.EECM-MPFQ, the current EECM software, is even faster. EECM, GMP-EECM, and EECM-MPFQ were introduced in the following paper:

• [eecm]41pp.(PDF)Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM using Edwards curves. Document ID: cb39208064693232e4751ec8f3494c43. URL: https://cr.yp.to/papers.html#eecm. Date: 2011.10.08. Supersedes:(PDF)2008.01.09.(PDF)2008.01.20.(PDF)2009.01.20.(PDF)2009.12.29.(PDF)2010.01.24.(PDF)2010.06.16.

GPU-ECM, a highly parallel low-memory EECM implementation for graphics cards, was introduced in the following paper:

• [gpuecm]20pp.(PDF)Daniel J. Bernstein, Tien-Ren Chen, Chen-Mou Cheng, Tanja Lange, Bo-Yin Yang. ECM on graphics cards. Document ID: 6904068c52463d70486c9c68ba045839. URL: https://cr.yp.to/papers.html#gpuecm. Date: 2009.01.27. (Supersedes:(PDF)Date: 2008.11.11.) Pages 483–501 in_Advances in cryptology—EUROCRYPT 2009, 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26–30, 2009, proceedings_, edited by Antoine Joux. Lecture Notes in Computer Science 5479. Springer, 2009. ISBN 978-3-642-01000-2.

A rewritten CUDA-ECM with several times better GPU performance was introduced in the following paper, along with speedups for Core 2, Phenom II, and Cell:

• [pc109]14pp.(PDF)Daniel J. Bernstein, Hsueh-Chung Chen, Ming-Shing Chen, Chen-Mou Cheng, Chun-Hung Hsiao, Tanja Lange, Zong-Cing Lin, Bo-Yin Yang. The billion-mulmod-per-second PC. Document ID: 5d0b03cf72f71d39d2ac129eb7e4c5d7. URL: https://cr.yp.to/papers.html#pc109\. Date: 2009.09.01. Workshop record of SHARCS'09: Special-purpose Hardware for Attacking Cryptographic Systems.

Even better choices of twisted Edwards curves were introduced in the following paper and integrated into EECM-MPFQ:

• [a1ecm]20pp.(PDF)Daniel J. Bernstein, Peter Birkner, Tanja Lange. Starfish on strike. Document ID: 44c7b02bb6796bb931f85794f77ef1b0. URL: https://cr.yp.to/papers.html#a1ecm. Date: 2010.06.14. Pages 61–80 in_LATINCRYPT 2010_, edited by Michel Abdalla and Paulo S. L. M. Barreto. Lecture Notes in Computer Science 6212. Springer, 2010.

Acknowledgments

Daniel J. Bernstein (https://cr.yp.to/djb.html) was supported by the U.S. National Science Foundation, grant number ITR-0716498. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation."

Peter Birkner (http://www.peter-birkner.de/), Tanja Lange (https://www.hyperelliptic.org/tanja), and Christiane Peters (http://www.win.tue.nl/~cpeters/) were supported by the European Commission through the ICT Programme under Contract ICT–2007–216676 ECRYPT-II.

Version

This is version 2017.01.22 of the index.html web page.