Constructing nonresidues in finite fields and the extended Riemann hypothesis

We present a new deterministic algorithm for the problem of constructing kth power nonresidues in finite fields F_pn, where p is prime and k is a prime divisor of pⁿ - 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.