Constructing nonresidues in finite fields and the extended Riemann hypothesis

Open Access
Publisher Website
Google Scholar
Abstract
We present a new deterministic algorithm for the problem of constructing k k th power nonresidues in finite fields F p n \mathbf {F}_{p^n} , where p p is prime and k k is a prime divisor of p n − 1 p^n-1 . We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed n n and p → ∞ p \rightarrow \infty , our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if k k is exponentially large. More generally, assuming the ERH, in time ( n log ⁡ p ) O ( n ) (n \log p)^{O(n)} we can construct a set of elements that generates the multiplicative group F p n ∗ \mathbf {F}_{p^n}^* . An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.

This publication has 22 references indexed in Scilit: