Novel RNS Parameter Selection for Fast Modular Multiplication
Gavin Xiaoxu Yao, Junfeng Fan, Ray C. C. Cheung, Ingrid M.R. Verbauwhede · IEEE Transactions on Computers · 2013
The parameter selection of Residue Number Systems (RNS) has a great impact on its computational efficiency. This paper shows that a base extension, the most costly operation in RNS Montgomery multiplication, can be more efficient when the intervals between the RNS moduli are small. We propose a systematic RNS parameter selection procedure and two methods to select RNS moduli that lead to a reduced complexity. Our experimental results confirm the advantages of the selected moduli.