Proving primality in essentially quartic random time. (English) Zbl 1144.11085

In July 2002 appeared online the preprint “Primes is in P”, by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena which describes a deterministic polynomial time algorithm (henceforth referred to as “AKS”) to determine the primality of an integer \(n\). The appearance of such an algorithm was totally unexpected and unleashed a feeding frenzy among the primality testing community, as they searched for improvements. The essence of AKS is succinctly described in the present paper as “combinatorics in a cyclotomic extension of \({\mathbb Z}/(n)\)” and the first improvements came mainly from fine-tuning the combinatorics, though also from sharpening bounds on quantities used the the algorithm. Many of these improvements were incorporated in the published version [M. Agrawal, N. Kayal and N. Saxena, Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)]. The published algorithm has complexity \(\widetilde{O}(\log n^{7.5})\), whereas in the preprint the complexity is only proved to be \(\widetilde{O}(\log n^{12})\) where the notation \(\widetilde O(m)\) means \(O(m\) polynomial in \(\log m)\)).
A fundamental advance was made by P. Berrizbeitia [Math. Comput. 74, 2043–2059 (2005; Zbl 1071.11071)]. The preprint appeared in 2003, who showed that, for \(n\) such that \(n^2-1\) is divisible by a power of 2 close to \((\log n)^2\), one can do the combinatorics in a Kummer, rather than cyclotomic, extension of \({\mathbb Z}/(n)\), and the resulting algorithm is \(\widetilde{O}(\log n^{4})\). Berrizbeitia’s ideas were taken up by Q. Cheng [Primality Proving via One Round in ECPP and One Iteration in AKS, to appear in J. Cryptology, Preprint at http://www.cs.ou.edu/~qchengpub.html], Mihailescu and Avanzi (unpublished) and Bernstein in the present paper. Chen showed how to apply Berrizbeitia’s algorithm when one has any prime divisor of \(n-1\) close to \((\log n)^2\). Bernstein extends the algorithm to the case that one has an arbitrary divisor \(e \approx (\log n)^2\) of \(n^d-1\), where \(d \in n^{o(1)}\). The existence of a suitable pair \((d,e)\) for any prime \(n\) is proved in the paper, as a consequence of a theorem of Odlyzko and Pomerance. The resulting algorithm runs in time \((\log n^{4+o(1)})\). The basic theorem is:
Let \(n,d\) and \(e\) be positive integers such that \(2^e-1 \geq n^{2d\lfloor\sqrt{e}\rfloor}\) and \(e\) divides \(n^d-1\). Let \(f\) be a monic polynomial in \({\mathbb Z}/(n)[y]\) of degree \(d\). Define \(R\) as the ring \({\mathbb Z}/(n)[y]/f\). Let \(r\) be an element of \(R\) such that \(r^{n^d-1} =1\) in \(R\), \(r^{(n^d-1)/q}-1\) is a unit in \(R\) for each prime \(q\) dividing \(e\), and \(r-1\) is a unit in \(R\). If \((x-1)^{n^d}=r^{(n^d-1)/e}x-1\) in the ring \(R[x]/(x^e-r)\) then \(n\) is a power of a prime.
In fact a slightly refined version of the theorem is proved. Careful estimates of constant factors are given, and issues relevant to implementation discussed. Also included is a section on the relation between the work of Mihailescu and Avanzi and the current paper. It is still problematic as to whether the algorithm is truly practical, and competitive with (hyper)elliptic curve algorithms or, indeed, the subexponential algorithm usually known as APRCL [see H. Cohen and H. W. Lenstra, jun., Math. Comput. 42, 297–330 (1984; Zbl 0578.10004)] which in practice is extremely efficient. In this respect the author conjectures that, in his algorithm, \(d=1\) is the only relevant case, since if \(d>1\) one can follow Chen (loc. cit.) and use an elliptic curve step to replace \(n\) by an auxiliary \(n^\prime\) that-one hopes- has suitable divisors of \(n^\prime -1\). Conjecturally, the elliptic curve step takes time \(O((\log n)^{3+o(1)}\), so is worthwhile – even if it has to be repeated several times in order to reduce to \(d=1\). Experiment seems to confirm this, but nothing is proved. Finally, it should be noted that all the AKS-type algorithms in the Berrizbeitia line introduce a random element. To the reviewer’s knowledge, the only strictly deterministic polynomial time primality test is the original, cyclotomic version of AKS.


11Y11 Primality


Full Text: DOI


[1] Juris Hartmanis , 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. · Zbl 0656.00030
[2] 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. · Zbl 0744.11065
[3] 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. · Zbl 0526.10004 · doi:10.2307/2006975
[4] Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in \( P\) (2002). URL: http://www.cse.iitk.ac.in/news/primality.html. · Zbl 1071.11070
[5] 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. · Zbl 0815.11063
[6] Daniel J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp. 67 (1998), no. 223, 1253 – 1283. · Zbl 0910.11057
[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. · Zbl 1093.11019
[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 \( 2004\), 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. · Zbl 1110.11038
[11] Pedro Berrizbeitia, Sharpening PRIMES is in P for a large family of numbers, (2002). URL: http://arxiv.org/abs/math.NT/0211334. · Zbl 1071.11071
[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. · Zbl 1122.68456
[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. · Zbl 1104.11056
[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. · Zbl 1189.94056
[15] Michael R. Fellows and Neal Koblitz, Self-witnessing polynomial-time complexity and prime factorization, Des. Codes Cryptogr. 2 (1992), no. 3, 231 – 235. · Zbl 0756.11042 · doi:10.1007/BF00141967
[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 and Joe Kilian, Primality testing using elliptic curves, J. ACM 46 (1999), no. 4, 450 – 472. · Zbl 1064.11503 · doi:10.1145/320211.320213
[18] Ronald L. Graham and Jaroslav Nešetřil , The mathematics of Paul Erdős. I, Algorithms and Combinatorics, vol. 13, Springer-Verlag, Berlin, 1997. · Zbl 0857.00027
[19] Torbjorn Granlund, GMP \( 4.1.3:\) GNU multiple precision arithmetic library, (2004). URL: http://www.swox.com/gmp/.
[20] 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. · Zbl 0869.11102 · doi:10.1007/978-3-642-60408-9_15
[21] 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. · Zbl 0900.68250
[22] 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. · doi:10.1007/BFb0074800
[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 and K. W. Roggenkamp , Orders and their applications, Lecture Notes in Mathematics, vol. 1142, Springer-Verlag, Berlin, 1985. · Zbl 0561.00005
[26] Jan van Leeuwen , Handbook of theoretical computer science. Vol. A, Elsevier Science Publishers, B.V., Amsterdam; MIT Press, Cambridge, MA, 1990. Algorithms and complexity. · Zbl 0712.68054
[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. · Zbl 1078.11069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.