An iterative modular multiplication algorithm in RNS

摘要

Most current cryptosystems need to compute modular multiplication with large numbers. Modular multiplication is a time-consuming operation, and thus many different techniques have been proposed for the acceleration. A novel approach, residue number system (RNS), which has the advantages of parallel, carry-free, and high-speed arithmetic, is usually used for large number computations. However, division and the magnitude comparison, which most modular multiplication algorithms involve, are difficult to be processed in RNS. In this paper, we present an iterative modular multiplication algorithm in RNS. A subtle iterative model, eliminating division and the magnitude comparison in modular multiplications, proposed by Chiou and Yang, and improved further by Leong et al., can be used to achieve our purpose. Our new algorithm has the property of easy parallelization and is more efficient than other iterative modular multiplication algorithms proposed previously.