Modular multiplicative inverse in Java

Hi, today we will see how to compute Modular multiplicative inverse in Java.

first of all, we should know what it is and where it is used.

So, Modular multiplicative inverse of an integer is an integer x such that the product (ax) is congruent to 1 concerning the modulus b where lies in the interval [0,m-1].

In mathematics, it can be written as:

(a*x) % b = 1

Application: Computation of the modular multiplicative inverse has many practical applications in the field of cryptography, i.e. public-key cryptography and the RSA Algorithm.

Please Remember there could be multiple ways to solve a particular problem as per your understanding.

Modular multiplicative inverse: Java Code

In this procedure, we will try all the numbers from 1 to b and check whether (a*x)%b is 1 or not.

class Main { 
  static int calmodInv(int a, int b) 
  { 
    a = a % b; 
    for (int x = 1; x < b; x++) 
    if ((a * x) % b == 1) 
      return x; 
    return 1; 
  } 
  
  public static void main(String args[]) 
  { 
    int a = 10, b = 21; 
    System.out.println(calmodInv(a, b)); 
  } 
}

Output:

19

Explanation: Since, (10 X 19) % 21 =1 that’s why 19 is the output. Time Complexity of this algorithm is O(m).

Tip:

We can also calculate Modular multiplicative inverse by using:

  1. Extended Euler’s GCD algorithm having time complexity O(Log m) but this algorithm will only work when a and b are coprime.
  2. Fermat’s Little theorem, having time complexity O(Log m) but this will work only when b is prime.

Now you understand how to compute Modular multiplicative inverse in java.

you may also read:

how to evaluate Modular Exponentiation in Java

Leave a Reply

Your email address will not be published. Required fields are marked *