|
|
Introduction to EECM
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:
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.
|