Title Of Paper:
Selected RNS Bases for Efficient Design of Montgomery Multiplication
Author's Name :  Elham Javadnoori, Saeed Setayeshi, Mohammad Kheirandish
KeyWords:  RSA, Montgomery Multiplication, RNS, Moduli Set
Pages:  10 -19
Volume: 2
Issue: 9
Year: 2014


During the last years, different fast hardware implementations of RSA encryption have been done. In RSA algorithm the base operation is modular exponentiation. An efficient approach for modular exponentiation is Montgomery multiplication which computes the remainders without any division. Residue number system (RNS), replace large numbers with their small residues and does the mathematical operations on its small residues in parallel and without carry propagation. RNS Montgomery multiplication, similar to Montgomery multiplication has no division and moreover it computes addition, subtraction, and multiplication in RNS and therefore it is more efficient. Moduli selection has a great impact on RNS efficiency. In previous works optimal moduli sets are reported and in this work we propose a moduli set that is more efficient than the previous works.

Full Text: