ECM using Edwards curves

Bernstein, Daniel; Birkner, Peter; Lange, Tanja; Peters, Christiane

doi:10.1090/S0025-5718-2012-02633-0

ECM using Edwards curves
HTML articles powered by AMS MathViewer

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

Math. Comp. 82 (2013), 1139-1179

DOI: https://doi.org/10.1090/S0025-5718-2012-02633-0

Published electronically: November 20, 2012

PDF

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

SPEED: software performance enhancement for encryption and decryption, 2007. http://www.hyperelliptic.org/SPEED. See [27].
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].
Erich Rothe, Topological proofs of uniqueness theorems in the theory of differential and integral equations, Bull. Amer. Math. Soc. 45 (1939), 606–613. MR 93, DOI 10.1090/S0002-9904-1939-07048-1
I. M. Kamenetzky, Sur l’interpolation au moyen des dérivées et sur les procédés d’interpolation correspondants. I, C. R. (Doklady) Acad. Sci. URSS (N.S.) 25 (1939), 356–358 (French). MR 2003
Daniel J. Bernstein, Arbitrarily tight bounds on the distribution of smooth integers, Number theory for the millennium, I (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 49–66. MR 1956218
Daniel J. Bernstein, Scaled remainder trees (2004). http://cr.yp.to/papers.html\#scaledmod. Citations in this document: §5.3.
Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 325–384. MR 2467550
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters, Twisted Edwards curves, Progress in cryptology—AFRICACRYPT 2008, Lecture Notes in Comput. Sci., vol. 5023, Springer, Berlin, 2008, pp. 389–405. MR 2482341, DOI 10.1007/978-3-540-68164-9_{2}6
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.
Daniel J. Bernstein, Peter Birkner, Tanja Lange, and Christiane Peters, Optimizing double-base elliptic-curve single-scalar multiplication, Progress in cryptology—INDOCRYPT 2007, Lecture Notes in Comput. Sci., vol. 4859, Springer, Berlin, 2007, pp. 167–182. MR 2570254, DOI 10.1007/978-3-540-77026-8_{1}3
Daniel J. Bernstein, Tien-Ren Chen, Chen-Mou Cheng, Tanja Lange, and Bo-Yin Yang, ECM on graphics cards, Advances in cryptology—EUROCRYPT 2009, Lecture Notes in Comput. Sci., vol. 5479, Springer, Berlin, 2009, pp. 483–501. MR 2538444, DOI 10.1007/978-3-642-01001-9_{2}8
Daniel J. Bernstein, Tanja Lange, Explicit-formulas database (2007). http://hyperelliptic.org/EFD. Citations in this document: §2.
Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on elliptic curves, Advances in cryptology—ASIACRYPT 2007, Lecture Notes in Comput. Sci., vol. 4833, Springer, Berlin, 2007, pp. 29–50. MR 2565722, DOI 10.1007/978-3-540-76900-2_{3}
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.
Daniel J. Bernstein and Tanja Lange, Analysis and optimization of elliptic-curve single-scalar multiplication, Finite fields and applications, Contemp. Math., vol. 461, Amer. Math. Soc., Providence, RI, 2008, pp. 1–19. MR 2436321, DOI 10.1090/conm/461/08979
Daniel J. Bernstein and Tanja Lange, A complete set of addition laws for incomplete Edwards curves, J. Number Theory 131 (2011), no. 5, 858–872. MR 2772476, DOI 10.1016/j.jnt.2010.06.015
Serdar Boztaş and Hsiao-Feng Lu (eds.), Applied algebra, algebraic algorithms and error-correcting codes, Lecture Notes in Computer Science, vol. 4851, Springer, Berlin, 2007. Available electronically at http://www.springerlink.com/content/n2687m5l2575/. MR 2640522, DOI 10.1007/978-3-540-77224-8
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].
M. Krein and V. Šmulian, On regularly convex sets in the space conjugate to a Banach space, Ann. of Math. (2) 41 (1940), 556–583. MR 2009, DOI 10.2307/1968735
S. Minakshi Sundaram, On non-linear partial differential equations of the parabolic type, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 479–494. MR 88
Romain Cosset, Factorization with genus 2 curves, Math. Comp. 79 (2010), no. 270, 1191–1208. MR 2600562, DOI 10.1090/S0025-5718-09-02295-9
Peter de Rooij, Efficient exponentiation using precomputation and vector addition chains, Advances in cryptology—EUROCRYPT ’94 (Perugia), Lecture Notes in Comput. Sci., vol. 950, Springer, Berlin, 1995, pp. 389–399. MR 1479665, DOI 10.1007/BFb0053453
Nelson Dunford, A mean ergodic theorem, Duke Math. J. 5 (1939), 635–646. MR 98
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.
Harold M. Edwards, A normal form for elliptic curves, Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 3, 393–422. MR 2318157, DOI 10.1090/S0273-0979-07-01153-6
P. Gaudry, Fast genus 2 arithmetic based on theta functions, J. Math. Cryptol. 1 (2007), no. 3, 243–265. MR 2372155, DOI 10.1515/JMC.2007.012
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.
Robert Fortet, Remarques sur les espaces uniformément convexes, C. R. Acad. Sci. Paris 210 (1940), 497–499. MR 2007
Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson, Twisted Edwards curves revisited, Advances in cryptology—ASIACRYPT 2008, Lecture Notes in Comput. Sci., vol. 5350, Springer, Berlin, 2008, pp. 326–343. MR 2546103, DOI 10.1007/978-3-540-89255-7_{2}0
Antoine Joux (ed.), Advances in cryptology—EUROCRYPT 2009, Lecture Notes in Computer Science, vol. 5479, Springer, Berlin, 2009. Available electronically at http://www.springerlink.com/content/r87064455272/. MR 2590599, DOI 10.1007/978-3-642-01001-9
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.
Kaoru Kurosawa (ed.), Advances in cryptology—ASIACRYPT 2007, Lecture Notes in Computer Science, vol. 4833, Springer, Berlin, 2007. Available electronically at http://www.springerlink.com/content/978-3-540-76899-9. MR 2590581, DOI 10.1007/978-3-540-76900-2
S. Minakshi Sundaram, On non-linear partial differential equations of the hyperbolic type, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 495–503. MR 89
B. Mazur, Rational isogenies of prime degree (with an appendix by D. Goldfeld), Invent. Math. 44 (1978), no. 2, 129–162. MR 482230, DOI 10.1007/BF01390348
James McKee, Subtleties in the distribution of the numbers of points on elliptic curves over a finite prime field, J. London Math. Soc. (2) 59 (1999), no. 2, 448–460. MR 1709178, DOI 10.1112/S0024610799007334
S. Minakshi Sundaram, On non-linear partial differential equations of the parabolic type, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 479–494. MR 88
Peter Lawrence Montgomery, An FFT extension of the elliptic curve method of factorization, ProQuest LLC, Ann Arbor, MI, 1992. Thesis (Ph.D.)–University of California, Los Angeles. MR 2688742
M. Krein and V. Šmulian, On regularly convex sets in the space conjugate to a Banach space, Ann. of Math. (2) 41 (1940), 556–583. MR 2009, DOI 10.2307/1968735
Josef Pieprzyk (ed.), Advances in cryptology—ASIACRYPT 2008, Lecture Notes in Computer Science, vol. 5350, Springer, Berlin, 2008. Available electronically at http://www.springerlink.com/content/m8090j388147/. MR 2590580, DOI 10.1007/978-3-540-89255-7
Arnaud Denjoy, Sur certaines séries de Taylor admettant leur cercle de convergence comme coupure essentielle, C. R. Acad. Sci. Paris 209 (1939), 373–374 (French). MR 50
Robert D. Silverman and Samuel S. Wagstaff Jr., A practical analysis of the elliptic curve factoring algorithm, Math. Comp. 61 (1993), no. 203, 445–462. MR 1122078, DOI 10.1090/S0025-5718-1993-1122078-7
K. Srinathan, C. Pandu Rangan, and Moti Yung (eds.), Progress in cryptology—INDOCRYPT 2007, Lecture Notes in Computer Science, vol. 4859, Springer, Berlin, 2007. Available electronically at http://www.springerlink.com/content/978-3-540-77025-1. MR 2574217, DOI 10.1007/978-3-540-77026-8
William Stein (editor), Sage Mathematics Software (Version 3.2.3), The Sage Group, 2009. http://www.sagemath.org. Citations in this document: §6.10.
Hiromi Suyama, Informal preliminary report (8), cited in [18] as personal communication and in [36] (1985). Citations in this document: §7.
Serge Vaudenay (ed.), Progress in cryptology—AFRICACRYPT 2008, Lecture Notes in Computer Science, vol. 5023, Springer, Berlin, 2008. MR 2528441, DOI 10.1007/978-3-540-68164-9
Paul Zimmermann, 50 largest factors found by ECM. http://www.loria.fr/~zimmerma/records/top50.html. Citations in this document: §1.
Paul Zimmermann and Bruce Dodson, 20 years of ECM, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 525–542. MR 2282947, DOI 10.1007/11792086_{3}7