Sharpening “Primes is in P” for a large family of numbers.

*(English)*Zbl 1071.11071The historical breakthrough of M. Agrawal, N. Kayal and N. Saxena’s “PRIMES is in \(P\)” [Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)] – paper we shall refer to under the name AKS – solved the complexity theoretical question PRIMES (distinguishing prime numbers from composites) in deterministic polynomial time.

After the publishing of AKS on the internet, several authors attempted to improve the practical performance of the AKS test. Among all, the paper under review suggests the most important improvement so far.

Let \(n\) be an integer to be tested for primality, \(m > \log^2(n)\) an integer. Let \(\mathbf A \supset \mathbb Z/n\mathbb Z\) be a ring which contains an \(m\)th root of unity, say \(\alpha \in \mathbf A\), with \(\Phi_m(\alpha) = 0\), with \(\Phi_m\) being the \(m\)th cyclotomic polynomial. Suppose that one has tested the following condition, written in the spirit of AKS: \[ (1 + X)^n \equiv 1 + X^n \bmod X^m - \alpha, \tag{1} \] the operations being performed over \(\mathbf A\). Berrizbeitia’s beautiful observation consists in the fact that, by Galois theory, the above test also implies: \[ (1 + \alpha^i \cdot X)^n \equiv 1 + \alpha^{ni} \cdot X^n \bmod X^m - \alpha, \quad i = 1, 2, \ldots, m. \tag{2} \] Practically this allows replacing \(O\left(\log^2(n)\right)\) tests required by all versions of AKS, including the improved one which was recently published in the Annals of Mathematics, by a single verification of 1. The cost one pays is loss of the deterministic quality of the test. However this loss is not so important, since in fact the idea of Berrizbeitia may lead to a test which depends on the generalized Riemann hypothesis in such a way, that if the expected run time is not reached, an explicite counter example to the famous conjecture results.

The version of Berrizbeitia’s test exposed in the paper under review deals with the particular case in which the ring \(\mathbf A\) has degree one or two over \(\mathbb Z/n\mathbb Z\) und the integer \(m\) is a power of \(2\). The general case can easily be deduced on the line of older cyclotomy tests and this was done by other authors after the publication of Berrizbeitia’s paper on the internet.

After the publishing of AKS on the internet, several authors attempted to improve the practical performance of the AKS test. Among all, the paper under review suggests the most important improvement so far.

Let \(n\) be an integer to be tested for primality, \(m > \log^2(n)\) an integer. Let \(\mathbf A \supset \mathbb Z/n\mathbb Z\) be a ring which contains an \(m\)th root of unity, say \(\alpha \in \mathbf A\), with \(\Phi_m(\alpha) = 0\), with \(\Phi_m\) being the \(m\)th cyclotomic polynomial. Suppose that one has tested the following condition, written in the spirit of AKS: \[ (1 + X)^n \equiv 1 + X^n \bmod X^m - \alpha, \tag{1} \] the operations being performed over \(\mathbf A\). Berrizbeitia’s beautiful observation consists in the fact that, by Galois theory, the above test also implies: \[ (1 + \alpha^i \cdot X)^n \equiv 1 + \alpha^{ni} \cdot X^n \bmod X^m - \alpha, \quad i = 1, 2, \ldots, m. \tag{2} \] Practically this allows replacing \(O\left(\log^2(n)\right)\) tests required by all versions of AKS, including the improved one which was recently published in the Annals of Mathematics, by a single verification of 1. The cost one pays is loss of the deterministic quality of the test. However this loss is not so important, since in fact the idea of Berrizbeitia may lead to a test which depends on the generalized Riemann hypothesis in such a way, that if the expected run time is not reached, an explicite counter example to the famous conjecture results.

The version of Berrizbeitia’s test exposed in the paper under review deals with the particular case in which the ring \(\mathbf A\) has degree one or two over \(\mathbb Z/n\mathbb Z\) und the integer \(m\) is a power of \(2\). The general case can easily be deduced on the line of older cyclotomy tests and this was done by other authors after the publication of Berrizbeitia’s paper on the internet.

Reviewer: Preda Mihailescu (Göttingen)

##### References:

[1] | 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 |

[2] | 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 · doi.org |

[3] | M. Agrawal, N. Kayal, and N. Saxena, Primes is in P, preprint, August 2002, posted in http://www.cse.iitk.ac.in/news/primality.html · Zbl 1071.11070 |

[4] | A. O. L. Atkin. Lecture notes of a conference, Boulder (Colorado). Manuscript, August 1986. |

[5] | Daniel J. Bernstein, An Exposition of the Agrawal-Kayal-Saxena Primality-Proving Theorem, preprint, August 2002, posted in http://cr.yp.to/papers. \(\textnormal{html}^\char93 \)aks |

[6] | Pedro Berrizbeitia and T. G. Berry, Biquadratic reciprocity and a Lucasian primality test, Math. Comp. 73 (2004), no. 247, 1559 – 1564. · Zbl 1090.11004 |

[7] | Pedro Berrizbeitia, T. G. Berry, and Juan Tena-Ayuso, A generalization of Proth’s theorem, Acta Arith. 110 (2003), no. 2, 107 – 115. · Zbl 1028.11001 · doi:10.4064/aa110-2-1 · doi.org |

[8] | H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297 – 330. · Zbl 0578.10004 |

[9] | Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. · Zbl 1088.11001 |

[10] | William Feller, An Introduction to Probability Theory and Its Applications. Vol. I, John Wiley & Sons, Inc., New York, N.Y., 1950. · Zbl 0077.12201 |

[11] | S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 316-329, 1986. |

[12] | Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. · Zbl 0712.11001 |

[13] | 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 · doi.org |

[14] | H. W. Lenstra Jr., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331 – 340. · Zbl 0531.10002 |

[15] | E. Lucas. Sur la recherche des grands nombres premiers. Assoc. Francaise p. l’Avanc. des Science. Comptes Rendus, 5:61-68, 1876. |

[16] | F. Proth. Théorèmes sur les nombres premiers. Comptes Rendus Acad. des Sciences, Paris 87:926, 1878. |

[17] | B. L. van der Waerden, Algebra. Vol 1, Translated by Fred Blum and John R. Schulenberger, Frederick Ungar Publishing Co., New York, 1970. B. L. van der Waerden, Algebra. Vol. 2, Translated by John R. Schulenberger, Frederick Ungar Publishing Co., New York, 1970. |

[18] | Hugh C. Williams, Édouard Lucas and primality testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, vol. 22, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. · Zbl 1155.11363 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.