Improved Three-Way Split Formulas for Binary Polynomial and Toeplitz Matrix Vector Products

Author

Cenk, Murat ; Negre, Christophe ; Hasan, M. Anwar

Author_Institution

Dept. of Electr. & Comput. Eng., Univ. of Waterloo, Waterloo, ON, Canada

Volume

62

Issue

7

fYear

2013

fDate

Jul-13

Firstpage

1345

Lastpage

1361

Abstract

In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that are an optimization of Sunar´s formulas. Then, we present formulas with five recursive multiplications based on field extension. In addition, we extend the latter formulas to TMVP. We evaluate the space and delay complexities when computations are performed in parallel and provide a comparison with best known methods.

Keywords

Toeplitz matrices; computational complexity; optimisation; polynomials; Sunar formula; TMVP; Toeplitz matrix vector product; binary polynomial multiplication; delay complexity; optimization; recursive multiplication; space complexity; three-way split formula; Complexity theory; Cryptography; Delay; Interpolation; Logic gates; Polynomials; Vectors; Binary polynomial; Complexity theory; Cryptography; Delay; Interpolation; Logic gates; Polynomials; Sunar formula; TMVP; Toeplitz matrices; Toeplitz matrix; Toeplitz matrix vector product; Vectors; binary polynomial multiplication; computational complexity; delay complexity; finite field; optimisation; optimization; polynomials; recursive multiplication; space complexity; subquadratic space complexity multiplier; three-way split formula;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.2012.96

Filename

6189332