Summary
|
For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE. |
|
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 DOI: 10.1587/transfun.E101.A.239 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)>>
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. | ||||||||||
| ||||||||||