Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

ECM using Edwards curves


Authors: Daniel J. Bernstein, Peter Birkner, Tanja Lange and Christiane Peters
Journal: Math. Comp. 82 (2013), 1139-1179
MSC (2010): Primary 11Y05; Secondary 11G05
Published electronically: November 20, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper introduces EECM-MPFQ, a fast implementation of the elliptic-curve method of factoring integers. EECM-MPFQ uses fewer modular multiplications than the well-known GMP-ECM software, takes less time than GMP-ECM, and finds more primes than GMP-ECM. The main improvements above the modular-arithmetic level are as follows: (1) use Edwards curves instead of Montgomery curves; (2) use extended Edwards coordinates; (3) use signed-sliding-window addition-subtraction chains; (4) batch primes to increase the window size; (5) choose curves with small parameters and base points; (6) choose curves with large torsion.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y05, 11G05

Retrieve articles in all journals with MSC (2010): 11Y05, 11G05


Additional Information

Daniel J. Bernstein
Affiliation: Department of Computer Science (MC 152), University of Illinois at Chicago, Chicago, Illinois 60607–7053
Email: djb@cr.yp.to

Peter Birkner
Affiliation: Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands
Email: pbirkner@fastmail.fm

Tanja Lange
Affiliation: Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands
Email: tanja@hyperelliptic.org

Christiane Peters
Affiliation: Department of Mathematics, Technical University of Denmark, 2800 Kgs. Lyngby, Denmark
Email: c.p.peters@mat.dtu.dk

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02633-0
PII: S 0025-5718(2012)02633-0
Keywords: Factorization, ECM, elliptic-curve method, curve selection, Edwards coordinates, extended Edwards coordinates.
Received by editor(s): December 29, 2009
Received by editor(s) in revised form: October 8, 2011
Published electronically: November 20, 2012
Additional Notes: Permanent ID of this document: cb39208064693232e4751ec8f3494c43. This work was supported in part by the European Commission through the ICT Programme under Contract ICT–2007–216676 ECRYPT-II, and in part by the National Science Foundation under grant ITR–0716498. This work was carried out while the fourth author was with Technische Universiteit Eindhoven; in part while the first author was visiting Technische Universiteit Eindhoven; and in part while the authors were visiting INRIA Nancy.
Article copyright: © Copyright 2012 by the authors