The Gaussian normal basis and its trace basis over finite fields

It is well known that normal bases are useful for implementations of finite fields in various applications including coding theory, cryptography, signal processing, and so on. In particular, optimal normal bases are desirable. When no optimal normal basis exists, it is useful to have normal bases with low complexity. In this paper, we study the type k (>= 1) Gaussian normal basis N of the finite field extension F-qn/F-q, which is a classical normal basis with low complexity. By studying the multiplication table of N, we obtain the dual basis of N and the trace basis of N via arbitrary medium subfields F-qm/F-q with m vertical bar n and 1 <= m <= n. And then we determine all self-dual Gaussian normal bases. As an application, we obtain the precise multiplication table and the complexity of the type 2 Gaussian normal basis and then determine all optimal type 2 Gaussian normal bases. (C) 2012 Elsevier Inc. All rights reserved.