Title :
Low Space Complexity Multiplication over Binary Fields with Dickson Polynomial Representation
Author :
Hasan, M. Anwar ; Negre, Christophe
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Waterloo, Waterloo, ON, Canada
fDate :
4/1/2011 12:00:00 AM
Abstract :
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.
Keywords :
Hankel matrices; Toeplitz matrices; computational complexity; matrix multiplication; polynomial approximation; Dickson polynomial representation; Hankel matrix vector product; Toeplitz matrix vector product; binary field representation; field element; field multiplication; linear space complexity; low space complexity multiplication; matrix-vector formulation; optimal normal basis; parallel multiplier; sequential multiplier structure; Binary field; Dickson basis; Toeplitz matrix; multiplier; parallel; sequential.;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2010.132
