Efficient multiplication using type $2$ optimal normal bases

In this paper we propose a new structure for multiplication using optimal normal bases of type $2$. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of $F_{q^{n}}$ to suitable polynomials of degree at most $n$ over $F_{q}$. These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization --- which resembles the FFT factorization of the DFT matrix --- allows to compute the transformation and its inverse using $O(n \log n)$ operations in $F_{q}$, rather than $O(n^{2})$ operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type $2$ from $2 M(n) + O(n)$ reported by Gao et al.~(2000)\nocite{gaogat00} to $M(n)+O(n \log n)$ operations in $F_{q}$, where $M(n)$ is the number of $F_{q}$-operations to multiply two polynomials of degree $n-1$ over $F_{q}$. We show that this cost is also smaller than other proposed multipliers for $n > 160$, values which are used in elliptic curve cryptography.