{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T03:08:00Z","timestamp":1781838480167,"version":"3.54.5"},"reference-count":47,"publisher":"American Mathematical Society (AMS)","issue":"282","license":[{"start":{"date-parts":[[2013,11,20]],"date-time":"2013-11-20T00:00:00Z","timestamp":1384905600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>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.<\/p>","DOI":"10.1090\/s0025-5718-2012-02633-0","type":"journal-article","created":{"date-parts":[[2012,11,20]],"date-time":"2012-11-20T10:02:14Z","timestamp":1353405734000},"page":"1139-1179","source":"Crossref","is-referenced-by-count":23,"title":["ECM using Edwards curves"],"prefix":"10.1090","volume":"82","author":[{"given":"Daniel","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Birkner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tanja","family":"Lange","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christiane","family":"Peters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2012,11,20]]},"reference":[{"key":"1","unstructured":"SPEED: software performance enhancement for encryption and decryption, 2007. \\url{http:\/\/www.hyperelliptic.org\/SPEED}. See [27]."},{"key":"2","doi-asserted-by":"crossref","unstructured":"Michel Abdalla, Paulo S. L. M. Barreto (editors), Progress in cryptology\u2014LATINCRYPT 2010, first international conference on cryptology and information security in Latin America, Puebla, Mexico, August 8\u201311, 2010, proceedings, Lecture Notes in Computer Science, 6212, Springer, 2010. See [9].","DOI":"10.1007\/978-3-642-14712-8"},{"key":"3","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1090\/S0002-9904-1939-07048-1","article-title":"Topological proofs of uniqueness theorems in the theory of differential and integral equations","volume":"45","author":"Rothe, Erich","year":"1939","journal-title":"Bull. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9904","issn-type":"print"},{"key":"4","first-page":"356","article-title":"Sur l\u2019interpolation au moyen des d\u00e9riv\u00e9es et sur les proc\u00e9d\u00e9s d\u2019interpolation correspondants. I","volume":"25","author":"Kamenetzky, I. M.","year":"1939","journal-title":"C. R. (Doklady) Acad. Sci. URSS (N.S.)"},{"key":"5","isbn-type":"print","first-page":"49","article-title":"Arbitrarily tight bounds on the distribution of smooth integers","author":"Bernstein, Daniel J.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/1568811268"},{"key":"6","unstructured":"Daniel J. Bernstein, Scaled remainder trees (2004). \\url{http:\/\/cr.yp.to\/papers.html#scaledmod}. Citations in this document: \u00a75.3."},{"key":"7","isbn-type":"print","first-page":"325","article-title":"Fast multiplication and its applications","author":"Bernstein, Daniel J.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521808545"},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-540-68164-9_26","article-title":"Twisted Edwards curves","author":"Bernstein, Daniel J.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540681595"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Daniel J. Bernstein, Peter Birkner, Tanja Lange, Starfish on strike, in Latincrypt 2010, [2] (2010), 62\u201380. \\url{http:\/\/eprint.iacr.org\/2010\/367}. Citations in this document: \u00a71.2.","DOI":"10.1007\/978-3-642-14712-8_4"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-540-77026-8_13","article-title":"Optimizing double-base elliptic-curve single-scalar multiplication","author":"Bernstein, Daniel J.","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540770251"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-01001-9_28","article-title":"ECM on graphics cards","author":"Bernstein, Daniel J.","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642010002"},{"key":"12","unstructured":"Daniel J. Bernstein, Tanja Lange, Explicit-formulas database (2007). \\url{http:\/\/hyperelliptic.org\/EFD}. Citations in this document: \u00a72."},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-76900-2_3","article-title":"Faster addition and doubling on elliptic curves","author":"Bernstein, Daniel J.","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540768999"},{"key":"14","doi-asserted-by":"crossref","unstructured":"Daniel J. Bernstein, Tanja Lange, Inverted Edwards coordinates, in AAECC 2007 [17] (2007), 20\u201327. \\url{http:\/\/eprint.iacr.org\/2007\/410}. Citations in this document: \u00a71.1, \u00a72.5.","DOI":"10.1007\/978-3-540-77224-8_4"},{"key":"15","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/461\/08979","article-title":"Analysis and optimization of elliptic-curve single-scalar multiplication","author":"Bernstein, Daniel J.","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9780821843093"},{"issue":"5","key":"16","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1016\/j.jnt.2010.06.015","article-title":"A complete set of addition laws for incomplete Edwards curves","volume":"131","author":"Bernstein, Daniel J.","year":"2011","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"17","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77224-8","volume-title":"Applied algebra, algebraic algorithms and error-correcting codes","volume":"4851","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540772231"},{"key":"18","unstructured":"Richard P. Brent, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149\u2013163. ISSN 0157\u20133055. \\url{http:\/\/maths.anu.edu.au\/ brent\/pub\/pub102.html}. Citations in this document: \u00a74.2, \u00a74.3, \u00a79.3, \u00a79.4, \u00a710.3. See [44]."},{"key":"19","doi-asserted-by":"publisher","first-page":"556","DOI":"10.2307\/1968735","article-title":"On regularly convex sets in the space conjugate to a Banach space","volume":"41","author":"Krein, M.","year":"1940","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"20","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/BF03046993","article-title":"On non-linear partial differential equations of the parabolic type","volume":"9","author":"Sundaram, S. Minakshi","year":"1939","journal-title":"Proc. Indian Acad. Sci., Sect. A."},{"issue":"270","key":"21","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.1090\/S0025-5718-09-02295-9","article-title":"Factorization with genus 2 curves","volume":"79","author":"Cosset, Romain","year":"2010","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BFb0053453","article-title":"Efficient exponentiation using precomputation and vector addition chains","author":"de Rooij, Peter","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540601767"},{"key":"23","first-page":"635","article-title":"A mean ergodic theorem","volume":"5","author":"Dunford, Nelson","year":"1939","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"24","unstructured":"Karl Dickman, On the frequency of numbers containing primes of a certain relative magnitude, Arkiv f\u00f6r Matematik, Astronomi och Fysik 22 (1930), 1\u201314. ISSN 0365-4133. Citations in this document: \u00a79.3."},{"issue":"3","key":"25","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1090\/S0273-0979-07-01153-6","article-title":"A normal form for elliptic curves","volume":"44","author":"Edwards, Harold M.","year":"2007","journal-title":"Bull. Amer. Math. Soc. (N.S.)","ISSN":"https:\/\/id.crossref.org\/issn\/0273-0979","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1515\/JMC.2007.012","article-title":"Fast genus 2 arithmetic based on theta functions","volume":"1","author":"Gaudry, P.","year":"2007","journal-title":"J. Math. Cryptol.","ISSN":"https:\/\/id.crossref.org\/issn\/1862-2976","issn-type":"print"},{"key":"27","unstructured":"Pierrick Gaudry, Emmanuel Thom\u00e9, The mpFq library and implementing curve-based key exchanges, in [1] (2007), 49\u201364. \\url{http:\/\/www.loria.fr\/ gaudry\/papers.en.html}. Citations in this document: \u00a74.6."},{"key":"28","first-page":"497","article-title":"Remarques sur les espaces uniform\u00e9ment convexes","volume":"210","author":"Fortet, Robert","year":"1940","journal-title":"C. R. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4036","issn-type":"print"},{"key":"29","isbn-type":"print","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-540-89255-7_20","article-title":"Twisted Edwards curves revisited","author":"Hisil, Huseyin","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540892540"},{"key":"30","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01001-9","volume-title":"Advances in cryptology---EUROCRYPT 2009","volume":"5479","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642010002"},{"key":"31","unstructured":"Alexander Kruppa, Am\u00e9liorations de la multiplication et de la factorisation d\u2019entier, Ph.D. thesis, Universit\u00e9 Henri Poincar\u00e9 Nancy I, 2010. \\url{http:\/\/tel.archives-ouvertes.fr\/tel-00477005\/en\/}. Citations in this document: \u00a77."},{"key":"32","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76900-2","volume-title":"Advances in cryptology---ASIACRYPT 2007","volume":"4833","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540768999"},{"key":"33","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/BF03046994","article-title":"On non-linear partial differential equations of the hyperbolic type","volume":"9","author":"Sundaram, S. Minakshi","year":"1939","journal-title":"Proc. Indian Acad. Sci., Sect. A."},{"issue":"2","key":"34","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01390348","article-title":"Rational isogenies of prime degree (with an appendix by D. Goldfeld)","volume":"44","author":"Mazur, B.","year":"1978","journal-title":"Invent. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-9910","issn-type":"print"},{"issue":"2","key":"35","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1112\/S0024610799007334","article-title":"Subtleties in the distribution of the numbers of points on elliptic curves over a finite prime field","volume":"59","author":"McKee, James","year":"1999","journal-title":"J. London Math. Soc. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"key":"36","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/BF03046993","article-title":"On non-linear partial differential equations of the parabolic type","volume":"9","author":"Sundaram, S. Minakshi","year":"1939","journal-title":"Proc. Indian Acad. Sci., Sect. A."},{"key":"37","volume-title":"An FFT extension of the elliptic curve method of factorization","author":"Montgomery, Peter Lawrence","year":"1992"},{"key":"38","doi-asserted-by":"publisher","first-page":"556","DOI":"10.2307\/1968735","article-title":"On regularly convex sets in the space conjugate to a Banach space","volume":"41","author":"Krein, M.","year":"1940","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"39","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89255-7","volume-title":"Advances in cryptology---ASIACRYPT 2008","volume":"5350","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540892540"},{"key":"40","first-page":"373","article-title":"Sur certaines s\u00e9ries de Taylor admettant leur cercle de convergence comme coupure essentielle","volume":"209","author":"Denjoy, Arnaud","year":"1939","journal-title":"C. R. Acad. Sci. Paris","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4036","issn-type":"print"},{"issue":"203","key":"41","doi-asserted-by":"publisher","first-page":"445","DOI":"10.2307\/2152967","article-title":"A practical analysis of the elliptic curve factoring algorithm","volume":"61","author":"Silverman, Robert D.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"42","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77026-8","volume-title":"Progress in cryptology---INDOCRYPT 2007","volume":"4859","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540770251"},{"key":"43","unstructured":"William Stein (editor), Sage Mathematics Software (Version 3.2.3), The Sage Group, 2009. \\url{http:\/\/www.sagemath.org}. Citations in this document: \u00a76.10."},{"key":"44","unstructured":"Hiromi Suyama, Informal preliminary report (8), cited in [18] as personal communication and in [36] (1985). Citations in this document: \u00a77."},{"key":"45","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68164-9","volume-title":"Progress in cryptology---AFRICACRYPT 2008","volume":"5023","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540681595"},{"key":"46","unstructured":"Paul Zimmermann, 50 largest factors found by ECM. \\url{http:\/\/www.loria.fr\/ zimmerma\/records\/top50.html}. Citations in this document: \u00a71."},{"key":"47","isbn-type":"print","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/11792086_37","article-title":"20 years of ECM","author":"Zimmermann, Paul","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540360759"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2013-82-282\/S0025-5718-2012-02633-0\/S0025-5718-2012-02633-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-282\/S0025-5718-2012-02633-0\/S0025-5718-2012-02633-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:30:44Z","timestamp":1776792644000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-282\/S0025-5718-2012-02633-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,20]]},"references-count":47,"journal-issue":{"issue":"282","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["S0025-5718-2012-02633-0"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2012-02633-0","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2012,11,20]]}}}