University of Waterloo
In this paper, the authors propose new schemes for subquadratic arithmetic complexity multiplication in binary fields using optimal normal bases. The schemes are based on a recently proposed method known as block recombination, which efficiently computes the sum of two products of Toeplitz matrices and vectors. Specifically, here they take advantage of some structural properties of the matrices and vectors involved in the formulation of field multiplication using optimal normal bases. This yields new space and time complexity results for corresponding bit parallel multipliers.