Mathematics of Computation

Author(s): Daniel J. Bernstein.
Journal: Math. Comp. 76 (2007), 389-403.
MSC (2000): Primary 11Y11
Posted: September 14, 2006
Retrieve article in: PDF DVI PostScript

Abstract: This paper presents an algorithm that, given a prime

, finds and verifies a proof of the primality of

in random time $(\operatorname{lg} n)^{4+o(1)}$ . Several practical speedups are incorporated into the algorithm and discussed in detail.

1.: Leonard M. Adleman, Ming-Deh A. Huang, Proceedings of the th annual ACM symposium on theory of computing, Association for Computing Machinery, New York, 1986. ISBN 0-89791-193-8. MR 0990047 (89j:69001)
2.: -, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, 1512, Springer-Verlag, Berlin, 1992. ISBN 3-540-55308-8. MR 1176511 (93g:11128)
3.: Leonard M. Adleman, Carl Pomerance, Robert S. Rumely On distinguishing prime numbers from composite numbers, Annals of Mathematics 117 (1983), 173-206. ISSN 0003-486X. MR 0683806 (84e:10008)
4.: Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in (2002). URL: http://www.cse.iitk.ac.in/news/primality.html.
5.: A. O. L. Atkin, Francois Morain, Finding suitable curves for the elliptic curve method of factorization, Mathematics of Computation 60 (1993), 399-405. ISSN 0025-5718. MR 1140645 (93k:11115)
6.: Daniel J. Bernstein, Detecting perfect powers in essentially linear time, Mathematics of Computation 67 (1998), 1253-1283. ISSN 0025-5718. URL: http://cr.yp.to/papers.html. MR 1464141 (98j:11121)
7.: Daniel J. Bernstein, Sharper ABC-based bounds for congruent polynomials, to appear, Journal de Théorie des Nombres de Bordeaux. ISSN 1246-7405. URL: http://cr.yp.to/papers.html#abccong. ID 1d9e079cee20138de8e119a99044baa3.
8.: Daniel J. Bernstein, Fast multiplication and its applications, to appear in Buhler-Stevenhagen Algorithmic number theory book. URL: http://cr.yp.to/papers.html#multapps. ID 8758803e61822d485d54251b27b1a20d.
9.: Daniel J. Bernstein, Distinguishing prime numbers from composite numbers: the state of the art in , submitted. URL: http://cr.yp.to/papers.html#prime2004. ID d72f09ae5b05f41a53e2237c53f5f276.
10.: Daniel J. Bernstein, Hendrik W. Lenstra, Jr., Jonathan Pila, Detecting perfect powers by factoring into coprimes. URL: http://cr.yp.to/papers.html#powers2. ID bbd41ce71e527d3c06295aadccf60979.
11.: Pedro Berrizbeitia, Sharpening PRIMES is in P for a large family of numbers, (2002). URL: http://arxiv.org/abs/math.NT/0211334.
12.: Qi Cheng, Primality proving via one round in ECPP and one iteration in AKS, (2003). URL: http://www.cs.ou.edu/~qcheng/pub.html.
13.: Qi Cheng, On the bounded sum-of-digits discrete logarithm problem in finite fields, (2004). URL: http://www.cs.ou.edu/~qcheng/pub.html.
14.: Qi Cheng, Daqing Wan, On the list and bounded distance decodibility of Reed-Solomon codes, (extended abstract), (2004). URL: http://www.cs.ou.edu/~qcheng/pub.html.
15.: Michael R. Fellows, Neal Koblitz Self-witnessing polynomial-time complexity and prime factorization, Designs, Codes and Cryptography 2 (1992), 231-235. ISSN 0925-1022. URL: http://cr.yp.to/bib/entries.html#1992/fellows. MR 1181730 (93e:68032)
16.: Shafi Goldwasser, Joe Kilian, Almost all primes can be quickly certified, in [1], (1986), 316-329; see also newer version [17].
17.: Shafi Goldwasser, Joe Kilian, Primality testing using elliptic curves, Journal of the ACM 46 (1999), 450-472; see also older version [16]. ISSN 0004-5411. MR 1812127 (2002e:11182)
18.: Ronald L. Graham, Jaroslav Nešetril, The mathematics of Paul Erdos. I, Algorithms and Combinatorics, 13, Springer-Verlag, Berlin, 1997. ISBN 3-540-61032-4. MR 1425172 (97f:00032)
19.: Torbjorn Granlund, GMP GNU multiple precision arithmetic library, (2004). URL: http://www.swox.com/gmp/.
20.: Sergei Konyagin, Carl Pomerance, On primes recognizable in deterministic polynomial time, in [18] (1997), 176-198. URL: http://cr.yp.to/bib/entries.html#1997/konyagin. MR 1425185 (98a:11184)
21.: Arjen K. Lenstra, Hendrik W. Lenstra, Jr., Algorithms in number theory, in [26] (1990), 673-715. URL: http://cr.yp.to/bib/entries.html#1990/lenstra-survey. MR 1127178
22.: Hendrik W. Lenstra, Jr., Galois theory and primality testing, in [25] (1985), 169-189. MR 0812498 (87g:11171)
23.: Martin Macaj, Some remarks and questions about the AKS algorithm and related conjecture, (2002). URL: http://thales.doa.fmph.uniba.sk/macaj/aksremarks.pdf.
24.: Preda Mihailescu, Roberto M. Avanzi, Efficient ``quasi''-deterministic primality test improving AKS, URL: http://www-math.uni-paderborn.de/~preda/.
25.: I. Reiner, K. W. Roggenkamp (editors), Orders and their applications: proceedings of the conference held in Oberwolfach, June -, Lecture Notes in Mathematics, 1142, Springer-Verlag, Berlin, 1985. ISBN 3-540-15674-7. MR 0812486 (86g:16003)
26.: Jan van Leeuwen (editor), Handbook of theoretical computer science, volume A: algorithms and complexity, Elsevier, Amsterdam, 1990. ISBN 0-444-88071-2. MR 1127166 (92d:68001)
27.: José Felipe Voloch, On some subgroups of the multiplicative group of finite ring, to appear, Journal de Théorie des Nombres de Bordeaux. ISSN 1246-7405. URL: http://www.ma.utexas.edu/users/voloch/preprint.html.

Daniel J. Bernstein
Affiliation: Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, Illinois 60607--7045
Email: djb@cr.yp.to

DOI: 10.1090/S0025-5718-06-01786-8
PII: S 0025-5718(06)01786-8
Received by editor(s): February 13, 2004
Received by editor(s) in revised form: December 9, 2004
Posted: September 14, 2006
Additional Notes: The author was supported by the National Science Foundation under grant DMS--0140542, and by the Alfred P. Sloan Foundation. He used the libraries at the Mathematical Sciences Research Institute, the University of California at Berkeley, and the American Institute of Mathematics.
Copyright of article: Copyright 2006, by the author

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS