Constructing nonresidues in finite fields and the extended Riemann hypothesis
Johannes A Buchmann, Victor Shoup · 1991
We describe a new deterministic algorithm for the problem of constructing k-th power nonresidues in finite fields GF(pn), 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 + m, our algorithm runs in polynomial time.Unlike previous algorithms for this problem, this polynomial time bound holds even if k is very large.More generally, assuming the ERH, in time (log p)"(n) we can construct a set of elements that generates GF(pn)*.