THE PRIMITIVE NORMAL BASIS THEOREM – WITHOUT A COMPUTER

Abstract

Given $q$ , a power of a prime $p$ , denote by $F$ the finite field ${\rm GF}(q)$ of order $q$ , and, for a given positive integer $n$ , by $E$ its extension ${\rm GF}(q^n)$ of degree $n$ . A primitive element of $E$ is a generator of the cyclic group $E^\ast$ . Additively too, the extension $E$ is cyclic when viewed as an $FG$ -module, $G$ being the Galois group of $E$ over $F$ . The classical form of this result – the normal basis theorem – is that there exists an element $\alpha \in E$ (an additive generator) whose conjugates $\{\alpha, \alpha^q, \ldots, \alpha^{q^{n-1}}\}$ form a basis of $E$ over $F; \alpha$ is a free element of $E$ over $F$ , and a basis like this is a normal basis over $F$ . The core result linking additive and multiplicative structure is that there exists $\alpha \in E$ , simultaneously primitive and free over $F$ . This yields a primitive normal basis over $F$ , all of whose members are primitive and free. Existence of such a basis for every extension was demonstrated by Lenstra and Schoof [5] (completing work by Carlitz [1, 2] and Davenport [4]).