Finite field arithmetic using quasi-normal bases (Q2370646)

Efficient multiplication in finite fields requires normal bases of low density: A basis \({\mathcal B}=\{\beta_1,\dots , \beta_n\}\) is called normal if it is fixed under Galois automorphisms. If we express the products \(\beta_i\beta_j\) with respect to the basis \({\mathcal B}\), then the density (sometimes also called complexity) measures the total number of nonzero coefficients in these expressions. Exponentiation is very easy if normal bases are used, and multiplication is rather easy if the density is small. It is well known that the finite field \({\mathbb F}_{q^n}\) is an \({\mathbb F}_q[x]\)-module. If \((n,q)=1\), we can write this module as a direct sum of irreducible submodules. Then all decompositions of \({\mathbb F}_{q^n}\) into submodules are easy to determine. The idea in the paper is to find ``normal bases'' for these submodules. A basis which is the union of such ``sub''-bases is called quasi-normal. Exponentiation of field elements which are expressed with respect to quasi-normal bases is only slightly more complex than in the normal basis case. Therefore, quasi-normal bases of low density seem to be a good alternative to normal bases.