The Dual Bases And Trace Bases Of Gauss Normal Baese Over Finite Fields

It is well known that normal bases over finite fields have been implemented efficiently in software, and hardware implementation, and the time complexity of multiplication using normal bases depends on the structure of the normal basis used, particularly on the complexity of the normal basis over finite fields. Therefore to determine the complexity for normal bases, especially Gauss normal bases over finite fields, is interesting. This paper obtains the upper and lower bounds of the complexity for the dual basis of a class of type (n, k) (k≥3) Gauss normal bases over finite fields. The present paper gives the explicit relationship of the complexity between Gauss normal bases and their dual bases over finite fields, and the explicit complexity for the dual basis of the Gauss normal basis N of Fgn over Fq in case that the multiplication table of N is given. Furthermore, this paper also gives the multiplication tables and complexities of the dual basis and trace basis for some special Gauss normal bases over finites field with even characteristics, and then proves that the trace basis is the optimal in this case.