Primality testing with Gaussian periods (Q1737980): Difference between revisions

The paper provides a deterministic algorithm which decides the primality of a natural number \(n\)\, with complexity \((\log n)^6(2+\log\log n)^c\)\, bits, \(c\)\, a real number effectively computable. This improves a previous result due to \textit{M. Agrawal} et al. [Ann. Math. (2) 160, No. 2, 781--793 (2004; Zbl 1071.11070)] with complexity that look similar, but with exponent \(21/2\)\, instead of \(6\). Both papers follow similar ideas using a mixture of algebraic and analytic number theory tools. The proof needs a result from additive number theory due to \textit{D. Bleichenbacher} [The continuous postage problem. Unpublished manuscript (2003)], (see Theorems 3 and 4 of the present paper) and it reasons in some ring extensions of \(\mathbb{Z}/n\mathbb{Z}\)\, (pseudofields, finite fields if \(n\)\, is a prime), extensions constructed following and improving the construction of finite fields of \textit{L. M. Adleman} and \textit{H. W. Lenstra jun.} [``Finding irreducible polynomials over finite fields'', in: Proceedings of the eighteenth annual ACM symposium on theory of computing, STOC 1986. New York, NY: Association for Computing Machinery (ACM), 350--355 (1986; \url{doi:10.1145/12130.12166})], which adds to \(\mathbb{Z}/p\mathbb{Z}\)\, a set of \textit{Gaussian periods} parametrized by a \textit{period system}. Section 1 enunciates the main result (Theorem 1) and the auxiliary results necessaries to prove it (Theorems 2 to 5) and Section 2 gives the definition of pseudofield and period system and states some properties of them whose proof is delayed to later. Then Section 3 gives the proof of Theorem 1 (see Algorithm 3.3) assuming the validity of the auxiliary results. The rest of the paper deals with the auxiliary results. Section 4 provides the proof of Theorem 2 (which gives a method to construct finite fields) and Sections 5 to 8 the proof of the properties of pseudofields states in Section 2. The following Sections are more analytic. Section 9 gives the proof of Theorem 3 (inspired by the result of Bleichenbacher) and Section 10 a stronger version of Theorem 4 (a number-theoretic application of Theorem 3). Sections 11 and 12 are devoted to the proof of Theorem 5 and finally Section 13 proves the existence of periodic systems.