Low complexity of a class of normal bases 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 improve the upper bounds for the complexity of the trace normal bases over finite fields and prove that these upper bounds can be reached for some extension with small degree. In addition, we construct a class of normal bases with low complexity by this way.