Digit-Serial Versatile Multiplier Based on a Novel Block Recombination of the Modified Overlap-Free Karatsuba Algorithm

摘要

Overlap-Free Karatsuba Algorithm (OFKA) combined with block recombination approach (OFKABR) can improve the complexity of the original OFKA to obtain efficient implementation of polynomial basis multiplication over finite field$GF(2^{m})$. In this paper, we have further proposed a modified OFKABR (MOFKABR) strategy to reduce the space and time complexities of the best-known method. The proposed strategy is also extended to obtain a low-complexity versatile multiplier, which is designed to support the generalized multiplication on a wider range of field size for$m_{1}leq mleq m_{lambda }$. Using the proposed MOFKABR approach, the proposed digit-serial versatile multiplier can achieve subquadratic space complexity when compared with the existing digit-serial versatile multipliers.