Cryptology ePrint Archive: Report 2008/016
ECM using Edwards curves
Daniel J. Bernstein and Peter Birkner and 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.
Category / Keywords: Factorization, ECM, elliptic-curve method, curve selection, Edwards coordinates, extended Edwards coordinates
Date: received 9 Jan 2008, last revised 8 Oct 2011
Contact author: tanja at hyperelliptic org
Available format(s): PDF | BibTeX Citation
Note: Updated paper with more constructions.
Version: 20111008:180328 (All versions of this report)
Short URL: ia.cr/2008/016
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]