The Montgomery Modular Inverse - Revisited

E. Savas and C. K. Koc

IEEE Transactions on Computers, 49(7):763-766, July 2000.

Abstract

We modify an algorithm given by Kaliski to compute the Montgomery inverse of an integer modulo a prime number. We also give a new definition of the Montgomery inverse, and introduce efficient algorithms for computing the classical modular inverse, the Kaliski-Montgomery inverse, and the new Montgomery inverse. The proposed algorithms are suitable for software implementations on general-purpose microprocessors.