Existence problems for generators of finite fields

Stephen D Cohen
Department of Mathematics, University of Glasgow

The multiplicative group of a finite field E is cyclic: a generator is a primitive element. If E is the extension GF(q^n) of F:=GF(q), then, additively, viewed as an FG-module (where G=Gal(E/F)), E is also cyclic: a generator is a free element of E over F. Classically, this is the normal basis theorem whereby E possesses an F-basis of the form {w, w^q, w^{q^2},..., w^{q^{n-1}}}. The notions of a primitive and a free element are largely independent but the existence of a primitive element of E, free over F was established by Lenstra and Schoof in 1987 (building on earlier work of Carlitz and of Davenport) using Gauss sums to tie together the multiplicative and additive aspects.

We shall discuss further existence problems with a view to obtaining results displaying a measure of completeness. For example, a recent result is that, for all q and all n >= 5, there exists a primitive element of E free over F with arbitrary (non-zero) E/F- trace and arbitrary (primitive) E/F-norm. The proof uses a refined expression in terms of Gauss sums, and a sieving technique with respect to the orders of both the multiplicative and additive characters involved.