Selfdual normal bases on \(\mathrm{GF}(q)\) (Q757537)

A basis \((b_0,b_1,\ldots,b_{n-1})\) for \(\mathrm{GF}(q^n)\) over \(\mathrm{GF}(q)\), where \(q\) is a prime-power, is said to be self-dual if \(\text{tr}(b_ib_j)=\delta_{ij}\) \((0\leq i,j\leq n-1)\), and normal if \(b_i=b_{qi}\) \((0\leq i\leq n-1)\) for some fixed \(b\). Self-dual normal bases exist under known simple conditions on \(q\) and \(n\), and play an important role in the development of efficient algorithms for arithmetic in finite fields. Let \(O_n\) be the group of \(n\times n\) orthogonal circulant matrices over \(\mathrm{GF}(q)\). The authors' key observation is that there is a natural action of \(O_n\) on \(\mathrm{GF}(q^n)\) under which the self-dual normal bases (if there are any) are permuted regularly. This enables them to derive an explicit formula for the number of self-dual normal bases.