On the complexity of the normal bases via prime Gauss period over finite fields

A formula on the complexity of the normal bases generated by prime Gauss period over finite fields is presented in terms of cyclotomic numbers. Then, the authors determine explicitly the complexity of such normal bases and their dual bases in several cases where the related cyclotomic numbers have been calculated. Particularly, the authors ˉnd several series of such normal bases with low complexity. This research is supported by the National Fundamental Science Research Program 973 of China under Grant No. 2004 CB3180000 and the State Key Lab. (Information Security) of China.