A New Fast Modular Arithmetic Method in Public Key Cryptography

摘要

Modular arithmetic is a fundamental operation and plays an important role in public key cryptosystem. A new method and its theory evidence on the basis of modular arithmetic with large integer modulus—changeable modulus algorithm is proposed to improve the speed of the modular arithmetic in the presented paper. For changeable modulus algorithm, when modular computation of modulo n is difficult, it can be realized by computation of modulo n—1 and n- 2 on the perquisite of easy modular computations of modulo n—1 and modulo n—2. The conclusion is that the new method is better than the direct method by computing the modular arithmetic operation with large modulus. Especially, when computations of modulo n~1 and modulo n—2 are easy and computation of modulo n is difficult, this new method will be faster and has more advantages than other algorithms on modular arithmetic. Lastly, it is suggested that the proposed method be applied in public key cryptography based on modular multiplication and modular exponentiation with large integer modulus effectively.