Paper 2008/016

ECM using Edwards curves

Daniel J. Bernstein, Peter Birkner, Tanja Lange, and Christiane Peters

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.

Note: Updated paper with more constructions.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
FactorizationECMelliptic-curve methodcurve selectionEdwards coordinatesextended Edwards coordinates
Contact author(s)
tanja @ hyperelliptic org
History
2011-10-08: last of 9 revisions
2008-01-14: received
See all versions
Short URL
https://ia.cr/2008/016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/016,
      author = {Daniel J.  Bernstein and Peter Birkner and Tanja Lange and Christiane Peters},
      title = {ECM using Edwards curves},
      howpublished = {Cryptology ePrint Archive, Paper 2008/016},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/016}},
      url = {https://eprint.iacr.org/2008/016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.