Primality testing with Gaussian periods

DOI10.4171/JEMS/861MaRDI QIDQ1737980zbMATH OpenWikidataFDO

Authors H. W. jun. Lenstra, Carl Pomerance

Publication date 24 April 2019

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4171/JEMS/861

constructing finite fields continuous Frobenius problem period system primality testing pseudo field

Primes in congruence classes (11N13) Inverse problems of additive number theory, including sumsets (11P70) Primality (11Y11)

Review text

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.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Primality testing with Gaussian periods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1737980)