Low Space Complexity Multiplication over Binary Fields with Dickson Polynomial Representation
Anwar Hasan, Christophe Négre · IEEE Transactions on Computers · 2010
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 field elements as Toeplitz or Hankel matrix-vector products. This provides a parallel multiplier which is subquadratic in space and logarithmic in time. Using the matrix-vector formulation of the field multiplication, we also present sequential multiplier structures with linear space complexity.