Subquadratic Space Complexity Multiplication over Binary Fields with Dickson Polynomial Representation

摘要

We study Dickson bases for binary field representation. Such a representation seems interesting when no optimal normal basis exists for the field. We express the product of two elements as Toeplitz or Hankel matrix vector product. This provides a parallel multiplier which is subquadratic in space and logarithmic in time.