An efficient modulo $p$ multiplication algorithm with moderate factors of $p+1$ and $p-1$

Modular multiplication plays an important role to several public-key cryptosystems such as the RSA cryptosystem. This paper proposes an efficient modulo $p$ multiplication algorithm with moderate factors of $p+1$ and $p-1$. In order to improve the RSA decryption performance, users can utilize our proposed algorithm and the strong prime criterion. It will prove that the decryption method based on our proposed algorithm can run at a speed almost 6.5 times faster than that of the traditional method, or almost 2 times faster than that of the method based on the Chinese Remainder Theorem. Furthermore, the proposed algorithm can greatly enhance the performance of RSA encryption.

Keywords

modular multiplication, modular exponentiation, RSA cryptosystem, strong prime

2010 Mathematics Subject Classification

65Y20, 68Q99

Full Text (PDF format)

Published 1 January 2007