Remote Access Mathematics of Computation
Green Open Access

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
DOI: https://doi.org/10.1090/S0025-5718-2012-02633-0
Published electronically: November 20, 2012
MathSciNet review: 3008853
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?)

  • 1. SPEED: software performance enhancement for encryption and decryption, 2007. http://www.hyperelliptic.org/SPEED. See [27].
  • 2. Michel Abdalla, Paulo S. L. M. Barreto (editors), Progress in cryptology--LATINCRYPT 2010, first international conference on cryptology and information security in Latin America, Puebla, Mexico, August 8-11, 2010, proceedings, Lecture Notes in Computer Science, 6212, Springer, 2010. See [9].
  • 3. A. O. L. Atkin, Francois Morain, Finding suitable curves for the elliptic curve method of factorization, Mathematics of Computation 60 (1993), 399-405. ISSN 0025-5718. http://www.lix.polytechnique.fr/~morain/Articles/articles.english.html. Citations in this document: §1.2, §7, §7.1. MR 93k:11115
  • 4. Michael A. Bennett, Bruce C. Berndt, Nigel Boston, Harold G. Diamond, Adolf J. Hildebrand, Walter Philipp (editors), Number theory for the millennium. I: papers from the conference held at the University of Illinois at Urbana-Champaign, Urbana, IL, May 21-26, 2000,
    A. K. Peters, Natick, Massachusetts, 2002. ISBN 1-56881-126-8. MR 2003h:11004. See [5].
  • 5. Daniel J. Bernstein, Arbitrarily tight bounds on the distribution of smooth integers, in Number Theory 2000 [4] (2002), 49-66. http://cr.yp.to/papers.html#psi. Citations in this document: §9.4. MR 1956218 (2004b:11135)
  • 6. Daniel J. Bernstein, Scaled remainder trees (2004). http://cr.yp.to/papers.html#scaledmod. Citations in this document: §5.3.
  • 7. Daniel J. Bernstein, Fast multiplication and its applications, in Algorithmic Number Theory [19] (2008), 325-384. http://cr.yp.to/papers.html#multapps. Citations in this document: §5.3. MR 2467550 (2010a:68186)
  • 8. Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, Christiane Peters, Twisted Edwards curves, in Africacrypt 2008 [45] (2008), 389-405. http://eprint.iacr.org/2008/013. Citations in this document: §2.2, §2.4, §2.5, §3, §7. MR 2482341 (2010e:11057)
  • 9. Daniel J. Bernstein, Peter Birkner, Tanja Lange, Starfish on strike, in Latincrypt 2010, [2] (2010), 62-80. http://eprint.iacr.org/2010/367. Citations in this document: §1.2.
  • 10. Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters, Optimizing double-base elliptic-curve single-scalar multiplication, in Indocrypt 2007 [42] (2007), 167-182. http://eprint.iacr.org/2007/414. Citations in this document: §1.1. MR 2570254 (2010k:94034)
  • 11. Daniel J. Bernstein, Tien-Ren Chen, Chen-Mou Cheng, Tanja Lange, Bo-Yin Yang, ECM on graphics cards, in Eurocrypt 2009 [30] (2009), 483-501. http://eprint.iacr.org/2008/480. Citations in this document: §1. MR 2538444
  • 12. Daniel J. Bernstein, Tanja Lange, Explicit-formulas database (2007). http://hyperelliptic.org/EFD. Citations in this document: §2.
  • 13. Daniel J. Bernstein, Tanja Lange, Faster addition and doubling on elliptic curves, in Asiacrypt 2007 [32] (2007), 29-50. http://eprint.iacr.org/2007/286. Citations in this document: §1.1, §2.2, §2.4, §2.9. MR 2565722 (2011d:11125)
  • 14. Daniel J. Bernstein, Tanja Lange, Inverted Edwards coordinates, in AAECC 2007 [17] (2007), 20-27. http://eprint.iacr.org/2007/410. Citations in this document: §1.1, §2.5.
  • 15. Daniel J. Bernstein, Tanja Lange, Analysis and optimization of elliptic-curve single-scalar multiplication, in Fq8 [38] (2008), 1-19. http://eprint.iacr.org/2007/455. Citations in this document: §1.1, §4.5. MR 2436321 (2010a:94049)
  • 16. Daniel J. Bernstein, Tanja Lange, A complete set of addition laws for incomplete Edwards curves, Journal of Number Theory, 131, 858-872. http://eprint.iacr.org/2009/580. Citations in this document: §2.9, §2.9, §2.9, §3. MR 2772476
  • 17. Serdar Boztas, Hsiao-Feng Lu, Applied algebra, algebraic algorithms and error-correcting codes, 17th international symposium, AAECC-17, Bangalore, India, December 16-20, 2007, proceedings, Lecture Notes in Computer Science, 4851, Springer, 2007. ISBN 978-3-540-77223-1. See [14]. MR 2640522 (2011a:94003)
  • 18. Richard P. Brent, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149-163. ISSN 0157-3055. http://maths.anu.edu.au/~brent/pub/pub102.html. Citations in this document: §4.2, §4.3, §9.3, §9.4, §10.3. See [44].
  • 19. Joe Buhler, Peter Stevenhagen, Algorithmic number theory: lattices, number fields, curves and cryptography, Mathematical Sciences Research Institute Publications, 44, Cambridge University Press, 2008. ISBN 978-0521808545. MR 2009h:11003. See [7].
  • 20. David V. Chudnovsky, Gregory V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Advances in Applied Mathematics 7 (1986), 385-434. MR 88h:11094. Citations in this document: §4.4, §4.4, §4.7.
  • 21. Romain Cosset, Factorization with genus 2 curves, Mathematics of Computation 79 (2010), 1191-1208. http://arxiv.org/pdf/0905.2325. Citations in this document: §4.7, §4.7, §4.7, §4.7. MR 2600562 (2011d:11289)
  • 22. Peter de Rooij, Efficient exponentiation using precomputation and vector addition chains, in Eurocrypt 1994 [23] (1995), 389-399. MR 1479665. Citations in this document: §5.6.
  • 23. Alfredo De Santis (editor), Advances in cryptology--EUROCRYPT '94, workshop on the theory and application of cryptographic techniques, Perugia, Italy, May 9-12, 1994, proceedings, Lecture Notes in Computer Science, 950, Springer, Berlin, 1995. ISBN 3-540-60176-7. MR 98h:94001. See [22].
  • 24. Karl Dickman, On the frequency of numbers containing primes of a certain relative magnitude, Arkiv för Matematik, Astronomi och Fysik 22 (1930), 1-14. ISSN 0365-4133. Citations in this document: §9.3.
  • 25. Harold M. Edwards, A normal form for elliptic curves, Bulletin of the American Mathematical Society 44 (2007), 393-422. http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html. Citations in this document: §2.2. MR 2318157 (2008b:14052)
  • 26. Pierrick Gaudry, Fast genus 2 arithmetic based on theta functions, Journal of Mathematical Cryptology 1 (2007), 243-265. http://www.loria.fr/~gaudry/publis/arithKsurf.pdf. Citations in this document: §4.7, §4.7. MR 2372155 (2009f:11156)
  • 27. Pierrick Gaudry, Emmanuel Thomé, The mpFq library and implementing curve-based key exchanges, in [1] (2007), 49-64. http://www.loria.fr/~gaudry/papers.en.html. Citations in this document: §4.6.
  • 28. Florian Hess, Sebastian Pauli, Michael E. Pohst (editors), Algorithmic number theory, proceedings of the 7th international symposium (ANTS-VII) held at the Technische Universität Berlin, Berlin, July 23-28, 2006, Lecture Notes in Computer Science, 4076, Springer, Berlin, 2006. ISBN 3-540-36075-1. MR 2007h:11001. See [47].
  • 29. Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson, Twisted Edwards curves revisited, in Asiacrypt 2008 [39] (2008). http://eprint.iacr.org/2008/522. Citations in this document: §1.1, §2.3, §2.6, §2.6. MR 2546103
  • 30. Antoine Joux (editor), Advances in cryptology--EUROCRYPT 2009, 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26-30, 2009, proceedings, Lecture Notes in Computer Science, 5479, Springer, 2009. ISBN 978-3-642-01000-2. See [11]. MR 2590599 (2010j:94007)
  • 31. Alexander Kruppa, Améliorations de la multiplication et de la factorisation d'entier, Ph.D. thesis, Université Henri Poincaré Nancy I, 2010. http://tel.archives-ouvertes.fr/tel-00477005/en/. Citations in this document: §7.
  • 32. Kaoru Kurosawa (editor), Advances in cryptology--ASIACRYPT 2007, 13th international conference on the theory and application of cryptology and information security, Kuching, Malaysia, December 2-6, 2007, proceedings, Lecture Notes in Computer Science, 4833, Springer, 2007. ISBN 978-3-540-76899-9. See [13]. MR 2590581 (2010i:94001)
  • 33. Hendrik W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics 126 (1987), 649-673. ISSN 0003-486X. MR 89g:11125. https://openaccess.leidenuniv.nl/bitstream/1887/3826/1/346_086.pdf. Citations in this document: §1, §9.4.
  • 34. Barry Mazur, Rational isogenies of prime degree, Inventiones Mathematicae 4 (1978), 129-162. Citations in this document: §6. MR 482230 (80h:14022)
  • 35. James McKee, Subtleties in the distribution of the numbers of points on elliptic curves over a finite prime field, Journal of the London Mathematical Society 59 (1999), 448-460. Citations in this document: §4.1, §9.4. MR 1709178 (2000g:11055)
  • 36. Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Mathematics of Computation 48 (1987), 243-264. ISSN 0025-5718. MR 88e:11130. http://www.ams.org/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf. Citations in this document §4.3, §4.4, §7, §7.7. See [44].
  • 37. Peter L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph.D. thesis, University of California at Los Angeles, 1992. ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz. Citations in this document: §5.4, §5.4, §7, §7, §9.3, §10.1. MR 2688742
  • 38. Gary L. Mullen, Daniel Panario, Igor E. Shparlinski (editors), Finite fields and applications: papers from the 8th international conference held in Melbourne, July 9-13, 2007, Contemporary Mathematics, 461, American Mathematical Society, 2008. ISBN 978-0-8218-4309-3. MR 2009h:11004. See [15].
  • 39. Josef Pieprzyk (editor), Advances in cryptology$ \,$--$ \,$ASIACRYPT 2008, 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7-11, 2008, Lecture Notes in Computer Science, 5350, 2008. ISBN 978-3-540-89254-0. See [29]. MR 2590580 (2010j:94005)
  • 40. John M. Pollard, Theorems on factorization and primality testing, Proceedings of the
    Cambridge Philosophical Society 76 (1974), 521-528. ISBN 0305-0041. MR 50:6992.
    http://cr.yp.to/bib/entries.html#1974/pollard. Citations in this document: §4.2, §4.3.
  • 41. Robert D. Silverman, Samuel S. Wagstaff, Jr., A practical analysis of the elliptic curve factoring algorithm, Mathematics of Computation 61 (1993), 445-462. http://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1122078-7/S0025-5718-1993-1122078-7.pdf. Citations in this document: §9.3. MR 1122078 (93k:11117)
  • 42. Kannan Srinathan, Chandrasekaran Pandu Rangan, Moti Yung (editors), Progress in cryptology--INDOCRYPT 2007, 8th international conference on cryptology in India, Chennai, India, December 9-13, 2007, proceedings, Lecture Notes in Computer Science, 4859, Springer, 2007. ISBN 978-3-540-77025-1. See [10]. MR 2574217 (2010g:94137)
  • 43. William Stein (editor), Sage Mathematics Software (Version 3.2.3), The Sage Group, 2009. http://www.sagemath.org. Citations in this document: §6.10.
  • 44. Hiromi Suyama, Informal preliminary report (8), cited in [18] as personal communication and in [36] (1985). Citations in this document: §7.
  • 45. Serge Vaudenay, Progress in cryptology$ \,$--$ \,$AFRICACRYPT 2008, First international conference on cryptology in Africa, Casablanca, Morocco, June 11-14, 2008, proceedings, Lecture Notes in Computer Science, 5023, Springer, 2008. ISBN 978-3-540-68159-5. See [8]. MR 2528441 (2009m:94064)
  • 46. Paul Zimmermann, 50 largest factors found by ECM. http://www.loria.fr/~zimmerma/records/top50.html. Citations in this document: §1.
  • 47. Paul Zimmermann, Bruce Dodson, 20 years of ECM, in ANTS VII [28] (2006), 525-542. http://www.loria.fr/~zimmerma/papers/40760525.pdf. Citations in this document: §1, §4.2, §4.3, §4.4, §4.5, §5.3, §7. MR 2282947 (2007j:11172)

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: https://doi.org/10.1090/S0025-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

American Mathematical Society