Efficient Multiplication Based on Dickson Bases over Any Finite Fields

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

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.11   pp.2060-2074
Publication Date: 2016/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.2060
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
finite field,  subquadratic space complexity multiplier,  Dickson basis,  Toeplitz matrix vector product,  block decomposition,  

Full Text: PDF>>
Buy this Article




Summary: 
We propose subquadratic space complexity multipliers for any finite field $mathbb{F}_{q^n}$ over the base field $mathbb{F}_q$ using the Dickson basis, where q is a prime power. It is shown that a field multiplication in $mathbb{F}_{q^n}$ based on the Dickson basis results in computations of Toeplitz matrix vector products (TMVPs). Therefore, an efficient computation of a TMVP yields an efficient multiplier. In order to derive efficient $mathbb{F}_{q^n}$ multipliers, we develop computational schemes for a TMVP over $mathbb{F}_{q}$. As a result, the $mathbb{F}_{2^n}$ multipliers, as special cases of the proposed $mathbb{F}_{q^n}$ multipliers, have lower time complexities as well as space complexities compared with existing results. For example, in the case that n is a power of 3, the proposed $mathbb{F}_{2^n}$ multiplier for an irreducible Dickson trinomial has about 14% reduced space complexity and lower time complexity compared with the best known results.