Constructing nonresidues in finite fields and the extended Riemann hypothesis

We present a new deterministic algorithm for the problem of constructing $k$th power nonresidues in finite fields $% \mathbf {F}_{p^n}$, where $p$ is prime and $k$ is a prime divisor of $p^n-1$. We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed $n$ and $p \rightarrow \infty$, 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 $% \mathbf {F}_{p^n}^*$. An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.