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

Jiangtao Han; Haining Fan

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 field subquadratic space complexity multiplier shifted polynomial basis Toeplitz matrix irreducible pentanomial.
Contact author(s): ivorstar @ gmail com
History: 2013-07-03: received
Short URL: https://ia.cr/2013/427
License: 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},
      url = {https://eprint.iacr.org/2013/427}
}