Low Area-Delay Complexity Digit-Level Parallel-In Serial-Out Multiplier Over GF(2m) Based on Overlap-Free Karatsuba Algorithm
Chiou‐Yng Lee, Jiafeng Xie · 2018
Overlap-free Karatsuba algorithm (OFKA) is one of the Karatsuba algorithms (KAs) which can be employed to reduce the computation complexity of fast/high-precision polynomial based multiplication (the space complexity of the product can be reduced from O(m2) to O(mlog23)). Meanwhile, digit-level (DL) finite field multipliers over GF(2m), generally can be categorized as DL parallel-in serial-out (DL-PISO) and DL serial-in parallel-out (DL-SIPO) styles, have gained substantial attentions in cryptographic related applications (such as elliptic curve cryptosystem (ECC)) recently due to their efficient performance in area-delay tradeoffs. In this paper, aim at deriving an efficient DL-PISO multiplier with sub-quadratic space complexity, we present a novel polynomial basis multiplication through a combination of three coherent interdependent efforts. First of all, a novel bivariate polynomial multiplication algorithm using two steps of reduction is presented. Then, a new DL-PISO polynomial basis multiplication algorithm using OFKA over GF(2m) is introduced as well as its corresponding structure. Finally, the complexity and comparison are detailed given to confirm the efficiency of the proposed DL-PISO multiplier over the existing DL-PISO and DL-SIPO designs, i.e., the proposed one has lower area-delay product (ADP) when compared with the competing ones. The proposed DL-PISO multiplier is highly regular and hence can be applied in many resource-constrained environments.