Low Complexity Multiplier Based on Dickson Basis Using Efficient 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.E98-A   No.11   pp.2283-2290
Publication Date: 2015/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.2283
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
Toeplitz matrix vector product,  Dickson basis,  subquadratic space complexity multiplier,  

Full Text: PDF>>
Buy this Article




Summary: 
A field multiplication in the extended binary field is often expressed using Toeplitz matrix-vector products (TMVPs), whose matrices have special properties such as symmetric or triangular. We show that such TMVPs can be efficiently implemented by taking advantage of some properties of matrices. This yields an efficient multiplier when a field multiplication involves such TMVPs. For example, we propose an efficient multiplier based on the Dickson basis which requires the reduced number of XOR gates by an average of 34% compared with previously known results.