Finite field arithmetic using quasi-normal bases

Efficient multiplication in finite fields Fqn requires Fq-bases of low density, i.e., such that the products of the basis elements have a sparse expression in the basis. In this paper we introduce a new family of bases: the quasi-normal bases. These bases generalize the notion of normal bases and provide simple exponentiation to the power q in Fqn. For some extension fields Fqn over Fq, we construct quasi-normal bases of low density.