This paper first obtains some basic theoretical results on trace-orthogonal normal bases of GF(qn) over GF(q): It shows that such a basis exists if and only if a self-dual normal basis exists (in fact, any such basis is equivalent to a self-dual one) and the paper gives several characterizations of the trace-orthogonal normal bases in terms of two matrices m and T (associated with every normal basis N) describing the multiplicative structure of GF(qn). The matrix T is actually the matrix used in investigating the complexity of the normal basis N. Using this fact, the paper also completely determines the trace-orthogonal optimal normal bases. In the special case q=2, n even, it then gives a simple construction associating with every self-dual normal basis N another such basis N* and relates the complexities of these two bases. This allows the paper to obtain an upper bound on the complexity of self-dual normal bases in this case which turns out to explain several entries in the available tables on computer searches regarding the complexity of normal bases. Finally, it gives a product construction for (trace-orthogonal) normal bases.
