JournalsjemsVol. 21, No. 4pp. 1229–1269

Primality testing with Gaussian periods

  • Hendrik W. Lenstra, Jr.

    Universiteit Leiden, Netherlands
  • Carl B. Pomerance

    Dartmouth College, Hanover, USA
Primality testing with Gaussian periods cover

A subscription is required to access this article.

Abstract

We exhibit a deterministic algorithm that, for some effectively computable real number cc, decides whether a given integer n>1n > 1 is prime within time logn)6(2+loglogn)c\mathrm {log} n)^6\cdot(2+\mathrm {log\log} n)^c. The same result, with 21/2 in place of 66, was proved by Agrawal, Kayal, and Saxena. Our algorithm follows the same pattern as theirs, performing computations in an auxiliary ring extension of Z/nZ\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 tt is a real number with 0<t10 < t \le1, and SS is an open subset of the interval (0,t)(0,t) with Sdx/x>t\int_S\mathrm d x/x > t, then each real number greater than or equal to 1 is in the additive semigroup generated by SS. A byproduct of our main result is an improved algorithm for constructing finite fields of given characteristic and approximately given degree.

Cite this article

Hendrik W. Lenstra, Jr., Carl B. Pomerance, Primality testing with Gaussian periods. J. Eur. Math. Soc. 21 (2019), no. 4, pp. 1229–1269

DOI 10.4171/JEMS/861