The complexity of the dual bases for Gauss normal bases of type (n,k)(k\geq 3) over finite fields

Abstract:

It is well known that normal bases over finite fields have been implemented efficiently in software. The hardware and time complexity of multiplication using normal bases depends on the structure of the normal basis used, particularly on the complexity of the normal basis. Therefore to determine the complexity for normal bases, especially Gauss normal bases over finite fields, is interesting. By properties for finite fields and elementary techniques, we obtain the upper and lower bounds of the complexity for the dual basis of a class of the type (n,k)(k\geq 3) Gauss normal bases, and determine the explicit complexity of the dual basis for the type (n,k)(k=1,2) Gauss normal bases over finite fields, which is an elementary proof for the main results given by Wan and Zhou in 2007.