A high-speed low-cost modulo P i multiplier with RNS arithmetic applications

Modulo P i multipliers are implemented by look-up tables when P i is small (5 bits or less) and by index calculus if P i is larger (6 bits or more). However, index calculus only works for prime moduli P i . In this letter, we introduce a new square-law multiplier that is useful for modulo P i multiplication where P i is any modulus. It is expected that this will have important applications in RNS arithmetic computing hardware.