Sharpening ``Primes is in P'' for a large family of numbers (Q5315434)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2203634
Language Label Description Also known as
default for all languages
No label defined
    English
    Sharpening ``Primes is in P'' for a large family of numbers
    scientific article; zbMATH DE number 2203634

      Statements

      Sharpening ``Primes is in P'' for a large family of numbers (English)
      0 references
      0 references
      8 September 2005
      0 references
      The historical breakthrough of \textit{M. Agrawal, N. Kayal} and \textit{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 \textit{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 \textbf{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.
      0 references

      Identifiers