{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:40:40Z","timestamp":1776786040846,"version":"3.51.2"},"reference-count":27,"publisher":"American Mathematical Society (AMS)","issue":"257","license":[{"start":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T00:00:00Z","timestamp":1189728000000},"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>\n                    This paper presents an algorithm that, given a prime\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , finds and verifies a proof of the primality of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"n\">\n                        <mml:semantics>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">n<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    in random time\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"left-parenthesis log base 10 n right-parenthesis Superscript 4 plus o left-parenthesis 1 right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>lg<\/mml:mi>\n                            <mml:mo>\n                              \u2061\n                              \n                            <\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:msup>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mn>4<\/mml:mn>\n                                <mml:mo>+<\/mml:mo>\n                                <mml:mi>o<\/mml:mi>\n                                <mml:mo stretchy=\"false\">(<\/mml:mo>\n                                <mml:mn>1<\/mml:mn>\n                                <mml:mo stretchy=\"false\">)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">(\\operatorname {lg} n)^{4+o(1)}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Several practical speedups are incorporated into the algorithm and discussed in detail.\n                  <\/p>","DOI":"10.1090\/s0025-5718-06-01786-8","type":"journal-article","created":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T16:50:02Z","timestamp":1162399802000},"page":"389-403","source":"Crossref","is-referenced-by-count":15,"title":["Proving primality in essentially quartic random time"],"prefix":"10.1090","volume":"76","author":[{"given":"Daniel","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2006,9,14]]},"reference":[{"key":"1","volume-title":"18th Annual ACM Symposium on Theory of Computing","year":"1989","issn-type":"print","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000"},{"key":"2","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090185","volume-title":"Primality testing and abelian varieties over finite fields","volume":"1512","author":"Adleman, Leonard M.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3540553088"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.2307\/2006975","article-title":"On distinguishing prime numbers from composite numbers","volume":"117","author":"Adleman, Leonard M.","year":"1983","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"4","unstructured":"Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in \ud835\udc43 (2002). URL: \\url{http:\/\/www.cse.iitk.ac.in\/news\/primality.html}."},{"issue":"201","key":"5","doi-asserted-by":"publisher","first-page":"399","DOI":"10.2307\/2153176","article-title":"Finding suitable curves for the elliptic curve method of factorization","volume":"60","author":"Atkin, A. O. L.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"223","key":"6","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1090\/S0025-5718-98-00952-1","article-title":"Detecting perfect powers in essentially linear time","volume":"67","author":"Bernstein, Daniel J.","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"7","unstructured":"Daniel J. Bernstein, Sharper ABC-based bounds for congruent polynomials, to appear, Journal de Th\u00e9orie des Nombres de Bordeaux. ISSN 1246-7405. URL: \\url{http:\/\/cr.yp.to\/papers.html#abccong}. ID 1d9e079cee20138de8e119a99044baa3."},{"key":"8","unstructured":"Daniel J. Bernstein, Fast multiplication and its applications, to appear in Buhler-Stevenhagen Algorithmic number theory book. URL: \\url{http:\/\/cr.yp.to\/papers.html#multapps}. ID 8758803e61822d485d54251b27b1a20d."},{"key":"9","unstructured":"Daniel J. Bernstein, Distinguishing prime numbers from composite numbers: the state of the art in 2004, submitted. URL: \\url{http:\/\/cr.yp.to\/papers.html#prime2004}. ID d72f09ae5b05f41a53e2237c53f5f276."},{"key":"10","unstructured":"Daniel J. Bernstein, Hendrik W. Lenstra, Jr., Jonathan Pila, Detecting perfect powers by factoring into coprimes. URL: \\url{http:\/\/cr.yp.to\/papers.html#powers2}. ID bbd41ce71e527d3c06295aadccf60979."},{"key":"11","unstructured":"Pedro Berrizbeitia, Sharpening PRIMES is in P for a large family of numbers, (2002). URL: \\url{http:\/\/arxiv.org\/abs\/math.NT\/0211334}."},{"key":"12","doi-asserted-by":"crossref","unstructured":"Qi Cheng, Primality proving via one round in ECPP and one iteration in AKS, (2003). URL: \\url{http:\/\/www.cs.ou.edu\/ qcheng\/pub.html}.","DOI":"10.1007\/978-3-540-45146-4_20"},{"key":"13","doi-asserted-by":"crossref","unstructured":"Qi Cheng, On the bounded sum-of-digits discrete logarithm problem in finite fields, (2004). URL: \\url{http:\/\/www.cs.ou.edu\/ qcheng\/pub.html}.","DOI":"10.1007\/978-3-540-28628-8_12"},{"key":"14","unstructured":"Qi Cheng, Daqing Wan, On the list and bounded distance decodibility of Reed-Solomon codes, (extended abstract), (2004). URL: \\url{http:\/\/www.cs.ou.edu\/ qcheng\/pub.html}."},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF00141967","article-title":"Self-witnessing polynomial-time complexity and prime factorization","volume":"2","author":"Fellows, Michael R.","year":"1992","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"16","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser, Joe Kilian, Almost all primes can be quickly certified, in [1], (1986), 316\u2013329; see also newer version [17].","DOI":"10.1145\/12130.12162"},{"issue":"4","key":"17","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":"18","series-title":"Algorithms and Combinatorics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60408-9","volume-title":"The mathematics of Paul Erd\\H{o}s. I","volume":"13","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540610324"},{"key":"19","unstructured":"Torbjorn Granlund, GMP 4.1.3: GNU multiple precision arithmetic library, (2004). URL: \\url{http:\/\/www.swox.com\/gmp\/}."},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-60408-9_15","article-title":"On primes recognizable in deterministic polynomial time","author":"Konyagin, Sergei","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540610324"},{"key":"21","isbn-type":"print","first-page":"673","article-title":"Algorithms in number theory","author":"Lenstra, A. K.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880712"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BFb0074800","article-title":"Galois theory and primality testing","author":"Lenstra, H. W., Jr.","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3540156747"},{"key":"23","unstructured":"Martin Macaj, Some remarks and questions about the AKS algorithm and related conjecture, (2002). URL: \\url{http:\/\/thales.doa.fmph.uniba.sk\/macaj\/aksremarks.pdf}."},{"key":"24","unstructured":"Preda Mih\u0103ilescu, Roberto M. Avanzi, Efficient \u201cquasi\u201d-deterministic primality test improving AKS, URL: \\url{http:\/\/www-math.uni-paderborn.de\/ preda\/}."},{"key":"25","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0074788","volume-title":"Orders and their applications","volume":"1142","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3540156747"},{"key":"26","isbn-type":"print","volume-title":"Handbook of theoretical computer science. Vol. A","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0444880712"},{"key":"27","unstructured":"Jos\u00e9 Felipe Voloch, On some subgroups of the multiplicative group of finite ring, to appear, Journal de Th\u00e9orie des Nombres de Bordeaux. ISSN 1246-7405. URL: \\url{http:\/\/www.ma.utexas.edu\/users\/voloch\/preprint.html}."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01786-8\/S0025-5718-06-01786-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01786-8\/S0025-5718-06-01786-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:46:38Z","timestamp":1776782798000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01786-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,14]]},"references-count":27,"journal-issue":{"issue":"257","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0025-5718-06-01786-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01786-8","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":[[2006,9,14]]}}}