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