Characterization and synthesis of self-complementary normal bases in finite fields (Q1096676)

A finite extension \(\Phi =GF(q^ n)\) of a finite field \(F=GF(q)\) has a self-complementary normal basis over F iff either n is odd or \(n\equiv 2\quad (mod 4)\) and q is even. This paper presents a complete characterization of square matrices A of order n over F such that the set \(\{A^{q^ k}\}_ 0^{n-1}\) is a self-complementary normal basis of a matrix representation \(\Phi\) over F. Specifically it is shown that a square matrix A of order n over F is a self-complementary normal basis generator for a matrix representation of \(\Phi\) over F iff A is a self- complementary normal matrix A which is defined as one with the properties (i) \(4A(i,j)=A(j,i);\) (ii) \(A(i,j)=A(i-j,-j)\) (indices mod n) (iii) \(\sum_{j}A[j]=uI[0],\) \(u\in \{1,-1\}\) where \(A[j]\) is the j-th column of A and \((iv)\quad A\quad q=S'AS\) where S is the cyclic shift matrix and S' its inverse. This characterization leads to a method of synthesizing irreducible polynomials of degree n over F whose roots form such a basis when one exists.