







[GaL92a]
Shuhong Gao and Hendrik W. Lenstra, Jr.,
``Optimal normal bases,''
Designs, Codes and Cryptography 2 (1992), 315323.
Abstract:
Let $K\subset L$ be a finite Galois extension of fields, of degree~$n$.
Let $G$ be the Galois group, and let $(\sigma\alpha)_{\sigma\in G}$ be
a normal basis for $L$ over~$K$. An argument due to Mullin, Onyszchuk,
Vanstone and Wilson (Discrete Appl.\ Math.\ {\sevenbf 22} (1988/89), 149161)
shows that the matrix that describes the map $x\mapsto\alpha x$ on this
basis has at least $2n1$ nonzero entries. If it contains exactly $2n1$
nonzero entries, then the normal basis is said to be optimal. In the present
paper we determine all optimal normal bases. In the case that $K$ is finite
our result confirms a conjecture that was made by Mullin et al. on the
basis of a computer search.