Constructing nonresidues in finite fields and the extended Riemann hypothesis

Johannes Buchmann, Victor Shoup

Research output: Contribution to journalArticlepeer-review


We present a new deterministic algorithm for the problem of constructing kth power nonresidues in finite fields Fpn, where p is prime and k is a prime divisor of pn - 1. We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed n and p → ∞, our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if k is exponentially large. More generally, assuming the ERH, in time (n log p)O(n) we can construct a set of elements that generates the multiplicative group F*pn. An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.

Original languageEnglish (US)
Pages (from-to)1311-1326
Number of pages16
JournalMathematics of Computation
Issue number215
StatePublished - Jul 1996

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Constructing nonresidues in finite fields and the extended Riemann hypothesis'. Together they form a unique fingerprint.

Cite this