Efficient Algorithm for Multi-Bit Montgomery Inverse Using Refined Multiplicative Inverse Modular <inline-formula> <tex-math notation="LaTeX">$2^K$ </tex-math></inline-formula>

Abstract

This paper makes two major contributions. First, we propose an algorithm to compute a multiplicative inverse modulo $2^{k}$ without using integer division by refining the Arazi–Qi algorithm. We then generalize this algorithm into a scalable algorithm to compute an inverse modulo $2^{kl}$ by iteratively exploiting a $k$ -bit-based process when the inverse modulo $2^{k}$ is given. Because of its scalability, this generalized algorithm can be cost-effectively implemented on hardware and applied to larger modulus operations by iteratively applying a processing unit. Furthermore, we highlight the possibility of the derivation of a binary representation of an inverse $P^{-1}$ in terms of a representation of $P$ and demonstrate this operation for up to eight bits. Second, using this direct relationship, we propose a multi-bit Montgomery inverse algorithm that is at least three times faster than the original version. Finally, we derive various properties of this algorithm and compare it with previous algorithms. This fast calculation of a Montgomery inverse is important for public key cryptographic applications, such as elliptic curve cryptosystems, because the relative speed of calculating a modular inverse for modular multiplication is a critical parameter for deciding which coordinate systems to adopt.

Keywords

• Cryptography
• high speed arithmetic-algorithms
• modular arithmetic
• modular inverse
• Montgomery inverse
• Montgomery multiplication