An Efficient CRT-Based Bit-Parallel Multiplier for Special Pentanomials

The Chinese remainder theorem (CRT)-based multiplier is a new type of hybrid bit-parallel multiplier, which can achieve nearly the same time complexity compared with the fastest multiplier known to date with reduced space complexity. However, the current CRT-based multipliers are only applicable to trinomials. In this article, we propose an efficient CRT-based bit-parallel multiplier for a special type of pentanomial
$x^m+x^{m-k}+x^{m-2k}+x^{m-3k}+1, 5k+1<m\leq 11k$
. Through transforming the non-constant part
$x^m+x^{m-k}+x^{m-2k}+x^{m-3k}$
into a binomial, we can obtain relatively simpler quotient and remainder computations, which lead to faster implementation with reduced space complexity compared with classic quadratic multipliers for the same pentanomials. Moreover, for some
$m$
, our proposal can match the fastest multipliers for irreducible Type I, Type II, and Type C.1 pentanomials of the same degree, but space complexities are roughly reduced by 8 percent.