A Novel Low Complexity Combinational RNS Multiplier Using Parallel Prefix Adder
Mohammad Reza Reshadinezhad, Farshad Kabiri Samani · 2013
Modular multiplication plays an important role in encryption. One of the encryption methods which need fast modular multiplication is RSA where large numbers are needed to empower large modules. In such methods, in order to show numbers, RNS is usually used with multiplication as the core. Modulo 2 n +1 multipliers are the primitive computational logic components widely used in residue arithmetic, digital signal processing, faulttolerant and cryptography. Here, two residue number system multipliers are introduced, both based on classifications of couples or triplets of input operands, which results in a low complexity RNS multiplier. The first modular multiplier is a combinational circuit which enables parallel prefix adder application in modulo 2 n +1. The second modulo 2 n +1 multiplier uses n+1 partial product, each with $n$ bit width, constructed by utilizing an inverted end-around-carry, carry save adder (CSA) tree and a parallel adder at the end. The performance and efficiently of the proposed multipliers are evaluated and compared with that of the earlier fastest modulo 2 n +1 multipliers. The proposed multipliers are considerably faster and more compact than that of the hardware implementations, which make them a viable option for efficient designs.