© 2003 by London Mathematical Society
© The London Mathematical Society
The Primitive Normal Basis Theorem – Without a Computer
Department of Mathematics, University of Glasgow Glasgow G12 8QW, sdc{at}maths.gla.ac.uk
Department of Mathematics, University of Glasgow Glasgow G12 8QW, sh{at}maths.gla.ac.uk
Received 16 July 2001. Revision received 10 March 2002.
Given q, a power of a prime p, denote by F the finite field GF(q) of order q, and, for a given positive integer n, by E its extension GF(qn) of degree n. A primitive element of E is a generator of the cyclic group E*. 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 
E (an additive generator) whose conjugates 
form a basis of E over F; 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 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]).