A high-speed low-cost modulo Pimultiplier with RNS arithmetic applications

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