The EMS Publishing House is now EMS Press and has its new home at

Please find all EMS Press journals and articles on the new platform.

Journal of the European Mathematical Society

Full-Text PDF (275 KB) | Metadata | Table of Contents | JEMS summary
Online access to the full text of Journal of the European Mathematical Society is restricted to the subscribers of the journal, who are encouraged to communicate their IP-address(es) to their agent or directly to the publisher at
Volume 21, Issue 4, 2019, pp. 1229–1269
DOI: 10.4171/JEMS/861

Published online: 2019-01-08

Primality testing with Gaussian periods

Hendrik W. Lenstra, Jr.[1] and Carl B. Pomerance[2]

(1) Universiteit Leiden, Netherlands
(2) Dartmouth College, Hanover, USA

We exhibit a deterministic algorithm that, for some effectively computable real number $c$, decides whether a given integer $n > 1$ is prime within time $\mathrm {log} n)^6\cdot(2+\mathrm {log\log} n)^c$. The same result, with 21/2 in place of $6$, was proved by Agrawal, Kayal, and Saxena. Our algorithm follows the same pattern as theirs, performing computations in an auxiliary ring extension of $\mathbb Z/n\mathbb Z$. We allow our rings to be generated by Gaussian periods rather than by roots of unity, which leaves us greater freedom in the selection of the auxiliary parameters and enables us to obtain a better run time estimate. The proof depends on results in analytic number theory and on the following theorem from additive number theory, which was provided by D. Bleichenbacher: if $t$ is a real number with $0 < t \le1$, and $S$ is an open subset of the interval $(0,t)$ with $\int_S\mathrm d x/x > t$, then each real number greater than or equal to 1 is in the additive semigroup generated by $S$. A byproduct of our main result is an improved algorithm for constructing finite fields of given characteristic and approximately given degree.

Keywords: Primality testing, constructing finite fields, Frobenius problem

Lenstra, Jr. Hendrik, Pomerance Carl: Primality testing with Gaussian periods. J. Eur. Math. Soc. 21 (2019), 1229-1269. doi: 10.4171/JEMS/861