Proving primality in essentially quartic random time

Bernstein, Daniel

doi:10.1090/S0025-5718-06-01786-8

Proving primality in essentially quartic random time
HTML articles powered by AMS MathViewer

by Daniel J. Bernstein PDF

Math. Comp. 76 (2007), 389-403

Abstract:

This paper presents an algorithm that, given a prime $n$, finds and verifies a proof of the primality of $n$ in random time $(\operatorname {lg} n)^{4+o(1)}$. Several practical speedups are incorporated into the algorithm and discussed in detail.

References

Juris Hartmanis (ed.), 18th Annual ACM Symposium on Theory of Computing, Elsevier, Inc., Amsterdam, 1989. Papers from the symposium held in Berkeley, California, May 28–30, 1986; J. Comput. System Sci. 38 (1989), no. 1. MR 990047
Leonard M. Adleman and Ming-Deh A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer-Verlag, Berlin, 1992. MR 1176511, DOI 10.1007/BFb0090185
Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in $P$ (2002). URL: http://www.cse.iitk.ac.in/news/primality.html.
A. O. L. Atkin and F. Morain, Finding suitable curves for the elliptic curve method of factorization, Math. Comp. 60 (1993), no. 201, 399–405. MR 1140645, DOI 10.1090/S0025-5718-1993-1140645-1
Daniel J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp. 67 (1998), no. 223, 1253–1283. MR 1464141, DOI 10.1090/S0025-5718-98-00952-1
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.
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.
Daniel J. Bernstein, Distinguishing prime numbers from composite numbers: the state of the art in $2004$, submitted. URL: http://cr.yp.to/papers.html#prime2004. ID d72f09ae5b05f41a53e2237c53f5f276.
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.
Pedro Berrizbeitia, Sharpening PRIMES is in P for a large family of numbers, (2002). URL: http://arxiv.org/abs/math.NT/0211334.
Qi Cheng, Primality proving via one round in ECPP and one iteration in AKS, (2003). URL: http://www.cs.ou.edu/~qcheng/pub.html.
Qi Cheng, On the bounded sum-of-digits discrete logarithm problem in finite fields, (2004). URL: http://www.cs.ou.edu/~qcheng/pub.html.
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.
Michael R. Fellows and Neal Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Des. Codes Cryptogr. 2 (1992), no. 3, 231–235. MR 1181730, DOI 10.1007/BF00141967
Shafi Goldwasser, Joe Kilian, Almost all primes can be quickly certified, in [1], (1986), 316–329; see also newer version [17].
Shafi Goldwasser and Joe Kilian, Primality testing using elliptic curves, J. ACM 46 (1999), no. 4, 450–472. MR 1812127, DOI 10.1145/320211.320213
Ronald L. Graham (ed.), The mathematics of Paul Erdős. I, Algorithms and Combinatorics, vol. 13, Springer-Verlag, Berlin, 1997. MR 1425172, DOI 10.1007/978-3-642-60408-9
Torbjorn Granlund, GMP $4.1.3:$ GNU multiple precision arithmetic library, (2004). URL: http://www.swox.com/gmp/.
Sergei Konyagin and Carl Pomerance, On primes recognizable in deterministic polynomial time, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 176–198. MR 1425185, DOI 10.1007/978-3-642-60408-9_{1}5
A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178
H. W. Lenstra Jr., Galois theory and primality testing, Orders and their applications (Oberwolfach, 1984) Lecture Notes in Math., vol. 1142, Springer, Berlin, 1985, pp. 169–189. MR 812498, DOI 10.1007/BFb0074800
Martin Macaj, Some remarks and questions about the AKS algorithm and related conjecture, (2002). URL: http://thales.doa.fmph.uniba.sk/macaj/aksremarks.pdf.
Preda Mihăilescu, Roberto M. Avanzi, Efficient “quasi”-deterministic primality test improving AKS, URL: http://www-math.uni-paderborn.de/~preda/.
I. Reiner and K. W. Roggenkamp (eds.), Orders and their applications, Lecture Notes in Mathematics, vol. 1142, Springer-Verlag, Berlin, 1985. MR 812486, DOI 10.1007/BFb0074788
Jan van Leeuwen (ed.), Handbook of theoretical computer science. Vol. A, Elsevier Science Publishers, B.V., Amsterdam; MIT Press, Cambridge, MA, 1990. Algorithms and complexity. MR 1127166
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.