{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:37:07Z","timestamp":1776800227414,"version":"3.51.2"},"reference-count":40,"publisher":"American Mathematical Society (AMS)","issue":"299","license":[{"start":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T00:00:00Z","timestamp":1468972800000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>We provide a framework for using elliptic curves with complex multiplication to determine the primality or compositeness of integers that lie in special sequences, in deterministic quasi-quadratic time. We use this to find large primes, including the largest prime currently known whose primality cannot feasibly be proved using classical methods.<\/p>","DOI":"10.1090\/mcom\/3001","type":"journal-article","created":{"date-parts":[[2015,7,20]],"date-time":"2015-07-20T09:13:38Z","timestamp":1437383618000},"page":"1461-1483","source":"Crossref","is-referenced-by-count":2,"title":["A framework for deterministic primality proving using elliptic curves with complex multiplication"],"prefix":"10.1090","volume":"85","author":[{"given":"Alexander","family":"Abatzoglou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alice","family":"Silverberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Sutherland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angela","family":"Wong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2015,7,20]]},"reference":[{"key":"1","unstructured":"A. Abatzoglou, A CM elliptic curve framework for deterministic primality testing on numbers of special form, University of California at Irvine PhD thesis, 2014."},{"key":"2","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2140\/obs.2013.1.1","article-title":"Deterministic elliptic curve primality proving for a special sequence of numbers","author":"Abatzoglou, Alexander","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781935107019"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal, Manindra","year":"2004","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"203","key":"4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.2307\/2152935","article-title":"Elliptic curves and primality proving","volume":"61","author":"Atkin, A. O. L.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"5","unstructured":"W. Bosma, Primality testing with elliptic curves, Doctoraalscriptie Report 85\u201312, Department of Mathematics, University of Amsterdam, 1985,  \\url{http:\/\/www.math.ru.nl\/ bosma\/pubs\/PRITwEC1985.pdf}."},{"issue":"4","key":"6","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-8858(86)90023-0","article-title":"Sequences of numbers generated by addition in formal groups and new primality and factorization tests","volume":"7","author":"Chudnovsky, D. V.","year":"1986","journal-title":"Adv. in Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-8858","issn-type":"print"},{"key":"7","isbn-type":"print","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387252827","edition":"2"},{"issue":"8","key":"8","doi-asserted-by":"publisher","first-page":"2398","DOI":"10.1016\/j.jnt.2007.12.009","article-title":"Elliptic curve primality tests for Fermat and related primes","volume":"128","author":"Denomme, Robert","year":"2008","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"9","unstructured":"J. Franke, T. Kleinjung, A. Decker, A. Gro\u00dfwendt, Format of the certificate (Version 0.1), available at \\url{http:\/\/www.math.uni-bonn.de\/people\/franke\/ptest\/fmt-0.1.pdf}."},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/070711761","article-title":"Faster integer multiplication","volume":"39","author":"F\u00fcrer, Martin","year":"2009","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"11","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC, Berkeley (California) (1986), 316\u2013329.","DOI":"10.1145\/12130.12162"},{"issue":"4","key":"12","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1145\/320211.320213","article-title":"Primality testing using elliptic curves","volume":"46","author":"Goldwasser, Shafi","year":"1999","journal-title":"J. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"13","isbn-type":"print","first-page":"290","article-title":"Pseudoprimes on elliptic curves","author":"Gordon, Daniel M.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/3110117916"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.jnt.2003.11.011","article-title":"An elliptic curve test for Mersenne primes","volume":"110","author":"Gross, Benedict H.","year":"2005","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"6","key":"15","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s00013-009-0065-9","article-title":"Primality testing through algebraic groups","volume":"93","author":"Gurevich, Alexander","year":"2009","journal-title":"Arch. Math. (Basel)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-889X","issn-type":"print"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/j.ffa.2011.07.011","article-title":"Deterministic primality tests based on tori and elliptic curves","volume":"18","author":"Gurevich, Alexander","year":"2012","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"key":"17","unstructured":"D. Harvey, J. van der Hoeven, G. Lecerf, Even faster integer multiplication, preprint available at \\url{http:\/\/arxiv.org\/abs\/1407.3360}, 2014."},{"issue":"4","key":"18","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1080\/10586458.2004.10504550","article-title":"Primality tests using algebraic groups","volume":"13","author":"Kida, Masanari","year":"2004","journal-title":"Experiment. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1058-6458","issn-type":"print"},{"key":"19","series-title":"Springer Monographs in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12893-0","volume-title":"Reciprocity laws","author":"Lemmermeyer, Franz","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540669574"},{"key":"20","unstructured":"F. Lemmermeyer, Reciprocity Laws: From Kummer to Hilbert, Chapter 12: Quadratic Reciprocity in Number Fields (Nov. 19, 2005), \\url{http:\/\/www.fen.bilkent.edu.tr\/ franz\/rl2\/rlb12.pdf}."},{"key":"21","isbn-type":"print","first-page":"99","article-title":"Elliptic curves and number-theoretic algorithms","author":"Lenstra, H. W., Jr.","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/0821801104"},{"key":"22","unstructured":"H. W. Lenstra Jr., Carl Pomerance, Primality testing with Gaussian periods, preprint available at \\url{http:\/\/www.math.dartmouth.edu\/ carlp\/aks041411.pdf}, 2011."},{"key":"23","unstructured":"P. Mihailescu, Dual elliptic primes and applications to cyclotomy primality proving, preprint available at \\url{http:\/\/arxiv.org\/abs\/0709.4113}, 2007."},{"issue":"257","key":"24","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1090\/S0025-5718-06-01890-4","article-title":"Implementing the asymptotically fast version of the elliptic curve primality proving algorithm","volume":"76","author":"Morain, F.","year":"2007","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"25","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","article-title":"Riemann\u2019s hypothesis and tests for primality","volume":"13","author":"Miller, Gary L.","year":"1976","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"issue":"177","key":"26","doi-asserted-by":"publisher","first-page":"315","DOI":"10.2307\/2007892","article-title":"Very short primality proofs","volume":"48","author":"Pomerance, Carl","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"27","first-page":"301","article-title":"Primality testing: variations on a theme of Lucas","volume":"201","author":"Pomerance, Carl","year":"2010","journal-title":"Congr. Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0384-9864","issn-type":"print"},{"issue":"1","key":"28","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","article-title":"Probabilistic algorithm for testing primality","volume":"12","author":"Rabin, Michael O.","year":"1980","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"12","key":"29","doi-asserted-by":"publisher","first-page":"2903","DOI":"10.1016\/j.jnt.2009.01.020","article-title":"Point counting on reductions of CM elliptic curves","volume":"129","author":"Rubin, K.","year":"2009","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"30","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"31","series-title":"Graduate Texts in Mathematics, No. 7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9884-4","volume-title":"A course in arithmetic","author":"Serre, J.-P.","year":"1973"},{"key":"32","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-5673-9","volume-title":"Local fields","volume":"67","author":"Serre, Jean-Pierre","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0387904247"},{"key":"33","series-title":"Publications of the Mathematical Society of Japan","isbn-type":"print","volume-title":"Introduction to the arithmetic theory of automorphic functions","volume":"11","author":"Shimura, Goro","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0691080925"},{"key":"34","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09494-6","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Silverman, Joseph H.","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780387094939","edition":"2"},{"key":"35","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0851-8","volume-title":"Advanced topics in the arithmetic of elliptic curves","volume":"151","author":"Silverman, Joseph H.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0387943285"},{"key":"36","unstructured":"N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at \\url{http:\/\/oeis.org}, 2010."},{"issue":"3","key":"37","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1216\/rmjm\/1181072041","article-title":"Counting points on CM elliptic curves","volume":"26","author":"Stark, H. M.","year":"1996","journal-title":"Rocky Mountain J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0035-7596","issn-type":"print"},{"key":"38","unstructured":"W. A. Stein et al., Sage Mathematics Software (Version 4.7.1), The Sage Development Team, 2011, \\url{http:\/\/www.sagemath.org}."},{"issue":"8","key":"39","doi-asserted-by":"publisher","first-page":"2697","DOI":"10.1090\/S0002-9939-2011-10839-6","article-title":"Primality tests for 2^{\ud835\udc5d}\u00b12^{(\ud835\udc5d+1)\/2}+1 using elliptic curves","volume":"139","author":"Tsumura, Yu","year":"2011","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"key":"40","isbn-type":"print","volume-title":"Primality test using elliptic curves with complex multiplication by Q-7","author":"Wong, Angela","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781303191954"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2016-85-299\/S0025-5718-2015-03001-4\/S0025-5718-2015-03001-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-299\/S0025-5718-2015-03001-4\/S0025-5718-2015-03001-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:45:43Z","timestamp":1776797143000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2016-85-299\/S0025-5718-2015-03001-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,20]]},"references-count":40,"journal-issue":{"issue":"299","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["S0025-5718-2015-03001-4"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3001","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":[[2015,7,20]]}}}