Some Properties of the Computation of the Modular Inverse with Applications in Cryptography

Abstract

In the field of cryptography, many algorithms rely on the computation of modular multiplicative inverses to ensure the security of their systems. In this study, we build upon our previous research by introducing a novel sequence, (zj)j≥0, that can calculate the modular inverse of a given pair of integers (a,n), i.e., a−1;mod,n. The computational complexity of this approach is O(a), which is more efficient than the traditional Euler’s phi function method, O(n,ln,n). Furthermore, we investigate the properties of the sequence (zj)j≥0 and demonstrate that all solutions of the problem belong to a specific set, I, that only contains the minimum values of (zj)j≥0. This results in a reduction of the computational complexity of our method, especially when a∼n and it also opens new opportunities for discovering closed-form solutions for the modular inverse.

Keywords

• extended-Euclid algorithm
• RSA algorithm
• modular multiplicative inverse
• public-key cryptography