Orders of Gauss periods in finite fields (Q1389144)

The problem of determining a fast algorithm to construct primitive roots in a finite field \({\mathbb F}_q\) of \(q\) elements is considered. All known algorithms for this problem work in two stages, first determining a small set guaranteed to contain a primitive element and, second, testing all elements of the set for primitivity. This last part requires the integer factorization of \(q-1\) which is not known to be obtainable in polynomial time. This problem is relaxed here to first, determine an element large order and second, to obtain such elements in some sufficiently dense sequence of fields, rather than all fields. The technique described here uses the notion of a Gauss period of type \((n,2)\), an element constructed in the following manner. For \(r=2n+1\) a prime not dividing \(q\) and \(\beta\) a primitive \(r\)th root of unity in \({\mathbb F}_{q^{2n}}\) then \[ \alpha = \beta + {\beta}^{-1} \in {\mathbb F}_{q^{2n}} \] is called a Gauss period of type \((n,2)\). It is shown here how such elements can be used to give an explicit polynomial-time computation of elements of exponentially large multiplicative order is some finite fields.