A new proof to complexity of dual basis of a type I optimal normal basis

Abstract

The complexity of dual basis of a type I optimal normal basis of ${\mathbb{F}}_{q^n}$ over ${\mathbb{F}}_q$ was determined to be $3n-3$ or $3n-2$ according as $q$ is even or odd, respectively, by Z.-X. Wan and K. Zhou in 2007. We give a new proof to this result by clearly deriving the dual of a type I optimal normal basis with the aid of a lemma on the dual of a polynomial basis.

arXiv comment7 pages