2012/11/20 by Daniel J. Bernstein, Peter Birkner, Tanja Lange +1 · 1 citation
Computer Science · Mathematics · #Cryptography and Residue Arithmetic #Polynomial and algebraic computation #Coding theory and cryptography #Mathematics #Factoring #Elliptic curve #Arithmetic #Edwards curve #Modular design #Algorithm #Discrete mathematics #Modular elliptic curve #Pure mathematics #Computer science #Quarter period
paper · pdf · doi:10.1090/s0025-5718-2012-02633-0
openalex publication_date 2012/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.