SEARCHING FOR PRIMITIVE ROOTS IN FINITE-FIELDS

Let GF(p(n)) be the finite field with p(n) elements, where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of GF(p(n)) that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in GF(p(n)). We present three results. First, we present a solution to this problem for the case where p is small, i.e., p = n(O)(1). Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case where p is large and n = 2. Third, we give a quantitative improvement of a theorem of Wang on the least primitive root for GF(p), assuming the ERH.