Fast Bit-Parallel Polynomial Basis Multiplier for GF(2m) Defined by Pentanomials Using Weakly Dual Basis

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

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.1   pp.322-331
Publication Date: 2013/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.322
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
finite field arithmetic,  pentanomials,  bit-parallel multiplier,  polynomial basis,  weakly dual basis,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, we derive a fast polynomial basis multiplier for GF(2m) defined by pentanomials xm+xk3+xk2+xk1+1 with 1 ≤ k1 < k2 < k3m/2 using the presented method by Park and Chang. The proposed multiplier has the time delay TA+(2+⌈log2(m-1)⌉) TX or TA+(3+⌈log2(m-1)⌉) TX which is the lowest one compared with known multipliers for pentanomials except for special types, where TA and TX denote the delays of one AND gate and one XOR gate, respectively. On the other hand, its space complexity is very slightly greater than the best known results.