Constructing normal bases in finite fields (Q2639102)

Let GF(q) denote the Galois field with q elements, and let \(GF(q^ n)\) denote an extension field of dimension n. If \(\alpha\) is an element of \(GF(q^ n)\) such that the conjugates \(\alpha,\alpha^ q,\alpha^{q^ 2},...,\alpha^{q^{n-1}}\) form a basis for \(GF(q^ n)\) over GF(q), \(\alpha\) is called a normal element of \(GF(q^ n)\) over GF(q). An element \(\beta\) of \(GF(q^ n)\) is called a primitive element if its multiplicative order is \(q^ n-1\). In this paper the authors show that a randomly chosen element of \(GF(q^ n)\) is normal over GF(q) with probability \(\Omega (1/\log_ en)\). They also give some improved lower bounds on the probability that a randomly chosen element of \(GF(q^ n)\) is simultaneously primitive and normal over GF(q). It should be noted that there is no known method for either generating or certifying a primitive element in (probabilistic) polynomial time. Based on some work of \textit{K. Hensel} [J. Reine Angew. Math. 103, 230-237 (1888; JFM 20.0073.03)] the authors then develop a probabilistic algorithm for finding a normal element of \(GF(q^ n)\) over GF(q) that is polynomial in n and log(q). For q ``small'' relative to n, an efficient deterministic variant is also given.