Optimal normal bases in \(GF(p^ n)\) (Q1112879)

The use of normal bases for multiplication in finite fields is examined. If \(N=\{\beta,\beta^ p,...,\beta^{p^{n-1}}\}\) is a normal basis of \(GF(p^ n)\) over GF(p) and \(A=\sum a_ i\beta^{p^ i}, \) \(B=\sum b_ j\beta^{p^ j} \) and \(C=AB=\Sigma c_ k\beta^{p^ k} \) then \(c_ k=\sum_{i}\sum_{j}\lambda_{ij}^{(k)}a_ ib_ j. \) It is easily established that \(c_ k\) can be obtained from the form \((\lambda_{ij}^{(0)})\) by cyclically shifting the coordinates \(a_ i\) and \(b_ j\) into k positions. If \(C_ N\) is the number of nonzero entries of this form, it is established that \(C_ N\geq 2n-1\). The basis N will be called optimal if \(C_ N=2n-1\). Some constructions of optimal normal bases are given under certain conditions and those over GF(2) receive particular attention. All optimal normal bases of \(GF(2^ n)\) over GF(2) are determined for \(n\leq 27\). In addition, those values of n less than 1200 for which an optimal normal basis is guaranteed by the theorems of the paper are found.