A Novel Low Complexity Combinational RNS Multiplier Using Parallel Prefix Adder
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 2n+1 multipliers are the primitive computational logic components widely used in residue arithmetic, digital signal processing, fault-tolerant 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 2n+1. The second modulo 2n+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 2n+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.
Keywords: Modular multiplier, residue number systems (RNS), modulo 2n+1 multiplier, parallel prefix adders, low complexity RNS multiplier.
Download Full-Text
ABOUT THE AUTHORS
Mohammad R. Reshadinezhad
He was born in Isfahan, Iran, in 1959.He received his B.S. and M.S. degree from the Electrical Engineering Department of University of Wisconsin, Milwaukee, USA in 1982 and 1985,respectively. He has been in position of lecturer as faculty of computer engineering in University of Isfahan since 1991. He also received the Ph.D Deggree in computer architecture from Shahid Beheshti University, Tehran, Iran, in 2012. He is currently Assistant Professor in Faculty of computer Engineering of Isfahan University. His research interests are digital arithmetic, Nanotechnology concerning CNFET, VLSI implementation, logic circuits designs and Cryptography.
Farshad Kabiri Samani
He received his B.S. and M.S. degree in computer engineering (hardware) from University of Najaf Abad, Iran and University of Arak, Iran in 2007 and 2010 respectively. He is currently working as a lecturer and researcher in Faculty of electrical and computer engineering department of Lenjan University, Lenjan, Iran. His research interests mainly focus on computer arithmetic algorithms and circuits, microprocessor architecture, and VLSI hardware designing.
Mohammad R. Reshadinezhad
He was born in Isfahan, Iran, in 1959.He received his B.S. and M.S. degree from the Electrical Engineering Department of University of Wisconsin, Milwaukee, USA in 1982 and 1985,respectively. He has been in position of lecturer as faculty of computer engineering in University of Isfahan since 1991. He also received the Ph.D Deggree in computer architecture from Shahid Beheshti University, Tehran, Iran, in 2012. He is currently Assistant Professor in Faculty of computer Engineering of Isfahan University. His research interests are digital arithmetic, Nanotechnology concerning CNFET, VLSI implementation, logic circuits designs and Cryptography.
Farshad Kabiri Samani
He received his B.S. and M.S. degree in computer engineering (hardware) from University of Najaf Abad, Iran and University of Arak, Iran in 2007 and 2010 respectively. He is currently working as a lecturer and researcher in Faculty of electrical and computer engineering department of Lenjan University, Lenjan, Iran. His research interests mainly focus on computer arithmetic algorithms and circuits, microprocessor architecture, and VLSI hardware designing.
