Modified Montgomery Modular Inversion with Reduced Number of Multiplications

In this paper, a modified algorithm to compute Montgomery modular Inverse that requires less number of Montgomery modular multiplications compared to the best known methods in literature is proposed. A method is also suggested for computing the Montgomery inverse using a modular multiplication algorithm recently proposed by Rainer et al. to compute the modular product. Our approaches are optimal in terms of computational delay and the practical efficiency has been evaluated for an operand length of 521-bit that is of interest to practical cryptographic applications. The proposed algorithms are expected to be of eminent importance for high-speed arithmetic