Paper 2013/427

Toeplitz matrix-vector product based GF(2^n) shifted polynomial basis multipliers for all irreducible pentanomials

Jiangtao Han and Haining Fan

Abstract

Besides Karatsuba algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design GF(2^n) subquadratic multipliers. However, when GF(2^n) elements are represented using a shifted polynomial basis, this approach is currently appliable only to GF(2^n)s generated by all irreducible trinomials and a special type of irreducible pentanomials, not all general irreducible pentanomials. The reason is that no transformation matrix, which transforms the Mastrovito matrix into a Toeplitz matrix, has been found. In this article, we propose such a transformation matrix and its inverse matrix for an arbitrary irreducible pentanomial. Because there is no known value of n for which either an irreducible trinomial or an irreducible pentanomial does not exist, this transformation matrix makes the TMVP approach a universal tool, i.e., it is applicable to all practical GF(2^n)s.

Note: Fix the [?] references in PDF.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Finite fieldsubquadratic space complexity multipliershifted polynomial basisToeplitz matrixirreducible pentanomial.
Contact author(s)
ivorstar @ gmail com
History
2013-07-03: received
Short URL
https://ia.cr/2013/427
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/427,
      author = {Jiangtao Han and Haining Fan},
      title = {Toeplitz matrix-vector product based GF(2^n) shifted polynomial basis multipliers for all irreducible pentanomials},
      howpublished = {Cryptology ePrint Archive, Paper 2013/427},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/427}},
      url = {https://eprint.iacr.org/2013/427}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.