[GaL92a]
Shuhong Gao and Hendrik W. Lenstra, Jr.,
``Optimal normal bases,''
Designs, Codes and Cryptography 2 (1992), 315-323.

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), 149--161) shows that the matrix that describes the map $x\mapsto\alpha x$ on this basis has at least $2n-1$ non-zero entries. If it contains exactly $2n-1$ non-zero 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.
 

Go Back to the Main Page