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

被引：25

作者：

Cenk, Murat ^{[1
]}

Negre, Christophe ^{[2
]}

Hasan, M. Anwar ^{[1
]}

机构：

[1] Univ Waterloo, Dept Elect & Comp Engn, Waterloo, ON N2L 3G1, Canada

[2] Univ Perpignan, Equipe DALI, F-66860 Perpignan, France

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2013年 / 62卷 / 07期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Binary polynomial; Toeplitz matrix; subquadratic space complexity multiplier; finite field; MULTIPLICATION; MULTIPLIERS; FIELDS;

D O I：

10.1109/TC.2012.96

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1345 / 1361

页数：17

共 14 条

[1]

[Anonymous], 1980, ARITHMETIC COMPLEXIT, DOI 10.1137/1.9781611970364

[2]

Bernstein DJ, 2009, LECT NOTES COMPUT SC, V5677, P317, DOI 10.1007/978-3-642-03356-8_19

[3]

Cenk M., 2011, P 18 INT C SEL AR CR

[4] Polynomial Multiplication over Finite Fields using Field Extensions and Interpolation [J].