Efficient Three-Way Split Formulas for Binary Polynomial Multiplication and Toeplitz Matrix Vector Product

Sun-Mi PARK  Ku-Young CHANG  Dowon HONG  Changho SEO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.1   pp.239-248
Publication Date: 2018/01/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
polynomial multiplication,  Toeplitz matrix vector product,  three-way split,  subquadratic space complexity multiplier,  finite field,  

Full Text: PDF(1.4MB)
>>Buy this Article


Summary: 
In this paper, we present a new three-way split formula for binary polynomial multiplication (PM) with five recursive multiplications. The scheme is based on a recently proposed multievaluation and interpolation approach using field extension. The proposed PM formula achieves the smallest space complexity. Moreover, it has about 40% reduced time complexity compared to best known results. In addition, using developed techniques for PM formulas, we propose a three-way split formula for Toeplitz matrix vector product with five recursive products which has a considerably improved complexity compared to previous known one.