TY - JOUR

T1 - A fast modular multiplication method

AU - Lou, Der Chyuan

AU - Chang, Chin Chen

PY - 1998/11

Y1 - 1998/11

N2 - 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.

AB - 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.

KW - Computer arithmetic

KW - Modular multiplication

KW - Public key cryptosystems

UR - http://www.scopus.com/inward/record.url?scp=0032203312&partnerID=8YFLogxK

M3 - 文章

AN - SCOPUS:0032203312

SN - 0267-6192

VL - 13

SP - 353

EP - 358

JO - Computer Systems Science and Engineering

JF - Computer Systems Science and Engineering

IS - 6

ER -