# 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

ais an integerxsuch that the product(ax)is congruent to1concerning the modulusbwherexlies 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:

**Extended Euler’s GCD algorithm**having**time complexity O(Log m)**but this algorithm will only work when**a**and**b**are**coprime**.**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:

## Leave a Reply

You must be logged in to post a comment.