A fast modular multiplication method

Modular multiplication (A×B mod N) is a fundamental operation in the implementations of modular exponentiation as needed in many cryptosystems, such as the RSA two-key cryptosystem. In 1994, Chiou and Yang proposed an efficient modular multiplication algorithm which needed only (n + 10) additions. In this paper, a method for computing large integer modular multiplication is proposed. The proposed method is based on the concept that the used partial products are skillfully stored, which can avoid generating the useless partial products, and thus the total number of modular additions is drastically reduced. On average, our proposed method yields three times faster than the conventional method, and results in about 25-36% time reduction as compared with Chiou and Yang's method for computing the modular multiplication. Furthermore, our new method can be combined with the previous related works for a better performance.