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 basis representations elements $\mathbb{F}_{q^{n}}$ suitable polynomials degree at most nover $\mathbb{F}_{q}$. These are multiplied any method which is implementation platform, then product converted back inverse above transformation. efficiency arises from special factorization its matrix into sparse matrices. This -- resembles FFT DFT allows compute and O(nlogn) operations in $\mathbb{F}_{q}$, rather than O(n2) needed general change basis. Using technique can reduce asymptotic cost 2 reported by Gao et al. (2000) M (n) + where number $\mathbb{F}_{q}$-operations multiply two ni¾? 1 over We show that also smaller other proposed multipliers n> 160, values used elliptic curve cryptography.