{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:39:44Z","timestamp":1743136784449,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":29,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781461472575"},{"type":"electronic","value":"9781461472582"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-1-4614-7258-2_12","type":"book-chapter","created":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T18:28:13Z","timestamp":1375381693000},"page":"159-186","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Primes Recognizable in Deterministic Polynomial Time"],"prefix":"10.1007","author":[{"given":"Sergei","family":"Konyagin","sequence":"first","affiliation":[]},{"given":"Carl","family":"Pomerance","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,5,20]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"L. M. Adleman and M.-D.\u00a0A.\u00a0Huang, Primality testing and two-dimensional abelian varieties over finite fields, Lecture Notes in Math. 1512, Springer-Verlag, Berlin, 1992, 142 pp.","key":"12_CR1","DOI":"10.1007\/BFb0090185"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"173","DOI":"10.2307\/2006975","volume":"117","author":"L M Adleman","year":"1983","unstructured":"L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. 117 (1983), 173\u2013206.","journal-title":"Ann. of Math."},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M Agrawal","year":"2004","unstructured":"M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Ann. of Math. 160 (2004), 781\u2013793.","journal-title":"Ann. of Math."},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"703","DOI":"10.2307\/2118576","volume":"140","author":"W R Alford","year":"1994","unstructured":"W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 140 (1994), 703\u2013722.","journal-title":"Ann. of Math."},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1090\/S0025-5718-06-01786-8","volume":"76","author":"D Bernstein","year":"2007","unstructured":"D. Bernstein, Proving primality in essentially quartic random time, Math. Comp. 76 (2007), 389\u2013403.","journal-title":"Math. Comp."},{"unstructured":"W. Bosma and M.-P. van der Hulst, Primality proving with cyclotomy, Ph.D. thesis, Amsterdam (1990).","key":"12_CR6"},{"key":"12_CR7","first-page":"1055","volume":"33","author":"J. Brillhart","year":"1981","unstructured":"J. Brillhart, M. Filaseta, and A. Odlyzko, On an irreducibility theorem of A.\u00a0Cohn, Can. J. Math. 33 (1981), 1055\u20131099.","journal-title":"J. Math."},{"key":"12_CR8","first-page":"620","volume":"29","author":"J Brillhart","year":"1975","unstructured":"J. Brillhart, D. H. Lehmer and J. L. Selfridge, New primality criteria and factorizations of 2\n                  m\n                \u2009\u00b1\u20091, Math. Comp. 29 (1975), 620\u2013647.","journal-title":"Math. Comp."},{"key":"12_CR9","first-page":"639","volume":"38","author":"J P Buhler","year":"1982","unstructured":"J. P. Buhler, R. E. Crandall and M. A. Penk, Primes of the form n!\u2009\u2009\u00b1\u20091 and 2 \u22c53 \u22c55\u2026p\u2009\u00b1\u20091, Math. Comp. 38 (1982), 639\u2013643.","journal-title":"Math. Comp."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","volume":"17","author":"E R Canfield","year":"1983","unstructured":"E. R. Canfield, P. Erd\u0151s and C. Pomerance, On a problem of Oppenheim concerning \u201cfactorisatio numerorum\u201d, J. Number Theory 17 (1983), 1\u201328.","journal-title":"J. Number Theory"},{"key":"12_CR11","volume-title":"Prime numbers: a computational perspective","author":"R Crandall","year":"2005","unstructured":"R. Crandall and C. Pomerance, Prime numbers:\u00a0a computational perspective, 2nd ed., Springer, New York, 2005.","edition":"2"},{"key":"12_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5927-3","volume-title":"Multiplicative number theory","author":"H Davenport","year":"1980","unstructured":"H. Davenport, Multiplicative number theory, 2nd ed., Springer-Verlag, New York, 1980.","edition":"2"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"404","DOI":"10.2307\/2307640","volume":"57","author":"P Erd\u0151s","year":"1950","unstructured":"P. Erd\u0151s, On almost primes, Amer. Math. Monthly 57 (1950), 404\u2013407.","journal-title":"Amer. Math. Monthly"},{"key":"12_CR14","doi-asserted-by":"crossref","first-page":"201","DOI":"10.5486\/PMD.1956.4.3-4.16","volume":"4","author":"P Erd\u0151s","year":"1956","unstructured":"P. Erd\u0151s, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201\u2013206.","journal-title":"Publ. Math. Debrecen"},{"issue":"\/67","key":"12_CR15","first-page":"73","volume":"40","author":"P. Erd\u0151s","year":"1966","unstructured":"P. Erd\u0151s and J. H. van Lint, On the number of positive integers\u2009\u2264\u2009x and free of prime factors\u2009>\u2009y, Simon Stevin 40 (1966\/67), 73\u201376.","journal-title":"Simon Stevin"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF00141967","volume":"2","author":"M R Fellows","year":"1992","unstructured":"M. R. Fellows and N. Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography 2 (1992), 231\u2013235.","journal-title":"Designs, Codes and Cryptography"},{"doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer, Deterministic and Las Vegas primality testing algorithms, in Proceedings of ICALP 85 (July 1985). Nafplion, Greece. W. Brauer, ed., Lecture Notes in Computer Science 194, Springer-Verlag, Berlin, 1985, pp. 199\u2013209.","key":"12_CR17","DOI":"10.1007\/BFb0015745"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A K Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, Jr. and L. Lov\u00e1sz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515\u2013534.","journal-title":"Math. Ann."},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0020-0190(79)90149-2","volume":"8","author":"H W Lenstra Jr","year":"1979","unstructured":"H. W. Lenstra, Jr., Miller\u2019s primality test, Information Processing Letters 8 (1979), 86\u201388.","journal-title":"Information Processing Letters"},{"unstructured":"H. W. Lenstra, jr and Carl Pomerance, Primality testing with Gaussian periods, www.math.dartmouth.edu\/~carlp\/aks041411.pdf","key":"12_CR20"},{"unstructured":"F. Pappalardi, On Artin\u2019s conjecture for primitive roots, Ph.D. thesis, McGill University (1993).","key":"12_CR21"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1090\/S0025-5718-1989-0968154-X","volume":"53","author":"J Pintz","year":"1989","unstructured":"J. Pintz, W. L. Steiger and E. Szemer\u00e9di, Infinite sets of primes with fast primality tests and quick generation of large primes, Math. Comp. 53 (1989), 399\u2013406.","journal-title":"Math. Comp."},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0025-5718-1987-0866117-4","volume":"48","author":"C Pomerance","year":"1987","unstructured":"C. Pomerance, Very short primality proofs, Math. Comp. 48 (1987), 315\u2013322.","journal-title":"Math. Comp."},{"key":"12_CR24","first-page":"301","volume":"201","author":"C Pomerance","year":"2010","unstructured":"C. Pomerance, Primality testing: variations on a theme of Lucas, Congressus Numerantium 201 (2010), 301\u2013312.","journal-title":"Congressus Numerantium"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0204018","volume":"4","author":"V R Pratt","year":"1975","unstructured":"V. R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), 214\u2013220.","journal-title":"SIAM J. Comput."},{"key":"12_CR26","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J B Rosser","year":"1962","unstructured":"J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64\u201394.","journal-title":"Illinois J. Math."},{"doi-asserted-by":"crossref","unstructured":"R. Solovay and V. Strassen, A fast Monte Carlo test for primality, SIAM J.\u00a0Comput. 6 (1977) 84\u201385; erratum 7 (1978), 118.","key":"12_CR27","DOI":"10.1137\/0206006"},{"doi-asserted-by":"crossref","unstructured":"I. M. Vinogradov, On the bound of the least non-residue of nth powers, Bull. Acad. Sci. USSR 20 (1926), 47\u201358 (= Trans. Amer. Math. Soc. 29 (1927), 218\u2013226).","key":"12_CR28","DOI":"10.1090\/S0002-9947-1927-1501385-5"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1090\/S0025-5718-09-02262-5","volume":"79","author":"B \u0179ra\u0142ek","year":"2010","unstructured":"B. \u0179ra\u0142ek, A deterministic version of Pollard\u2019s p \u2212 1 algorithm, Math. Comp. 79 (2010), 513\u2013533.","journal-title":"Math. Comp."}],"container-title":["The Mathematics of Paul Erd\u0151s I"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4614-7258-2_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T16:50:15Z","timestamp":1706201415000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-1-4614-7258-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9781461472575","9781461472582"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-1-4614-7258-2_12","relation":{},"subject":[],"published":{"date-parts":[[2013]]},"assertion":[{"value":"20 May 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}