Cryptology ePrint Archive: Report 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.
Category / Keywords: foundations / Finite field, subquadratic space complexity multiplier, shifted polynomial basis, Toeplitz matrix, irreducible pentanomial.
Date: received 26 Jun 2013, last revised 2 Jul 2013
Contact author: ivorstar at gmail com
Available format(s): PDF | BibTeX Citation
Note: Fix the [?] references in PDF.
Version: 20130703:081634 (All versions of this report)
Short URL: ia.cr/2013/427
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]