Searching for primitive roots in finite fields

Abstract:

Let ${\text {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 ${\text {GF}}({p^n})$ that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in ${\text {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 ${\text {GF}}(p)$, assuming the ERH.