LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles.
Sign Up to like articles & get recommendations!
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… Click to show full abstract
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+1xm+xm-k+xm-2k+xm-3k+1,5k+1<m≤11k. Through transforming the non-constant part $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}$xm+xm-k+xm-2k+xm-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$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.
