Introduction
In modular multiplicative inverse, two numbers are provided, ‘a’ and ‘m’, such that the given condition is satisfied:
The value of ‘x’ lies in the range of {1, 2, 3, …, m - 1}.
Note: ‘x’ can never become 0. As a * 0 mod ‘m’ can never be 1.
If you know the values of ‘a’ and ‘m’, how can you figure out the value of ‘x’? Come, let’s figure it out in detail.
Working:
So, through this approach, we are looking for an integer solution for ‘x’. Let’s take an example,
In other words, what we need to multiply with 5 and divide the result by 7, such that 3 becomes the remainder
One way to solve for x is the brute force approach. In the brute force approach, values from 1 to (m - 1) are plotted in the equation and are checked if the given criterion is fulfilled. In the above example, values from 1 to 6 are plotted and checked to see if they produce the result we are looking for.
The multiplicative inverse of a mod m exists if gcd(a,m) is 1 or a and m are relatively prime.
If a=5 and m=7, the output will be 3. Since 5 * 3 mod 7 = 1, 3 is modulo inverse of 5(under 7).
C++ code for brute force approach:
Naive Approach:
| /* C++ naive approach code to find The multiplicative inverse of a mod m */ #include <iostream> using namespace std; /* A function that returns the value of x calculated in basic approach */ int Find_mod_Inverse(int a, int m) { for (int i = 1; i < m; i++) { if (((a % m) * (i % m)) % m == 1) { // Here i is the value of x return i; } } } // Driver code int main() { int a = 5, m = 7; cout<<"The value of x is"<<" "; // Function call cout << Find_mod_Inverse(a, m); return 0; } |
Output:
| The value of x is 3 |
Time Complexity: O(m)
In the naive approach, we check for every number from 1 to m, so, the time complexity is O(m).
Space Complexity: O(1)
As constant space is used in this approach hence, the space complexity is O(1).
Efficient Approach:
This approach can only work if ‘a’ and ‘m’ are coprime to each other, i.e., gcd(a, m) = 1. The main idea is based on an extended Euclid algorithm. The idea is to take two integers a and b and find their gcd as well as the value of x and y.
To simplify the equation further, we put b = m. Since we already know that the gcd of a and m is prime, we can use the gcd value as 1.
Taking modulo in both sides, the equation becomes:
The second term can be easily removed as for any integer y, taking mod with m is always zero. So, the final equation looks like this:
x can be found out using the Extended Euclid Algorithm, which is the multiplicative inverse of a.
Recursive Approach using Extended Euclid’s Algorithm:
| /* C++ code for modular multiplicative inverse using an efficient approach of Extended Euclid Algorithm */ #include <iostream> using namespace std; // Function for extended Euclidean Algorithm int Find_gcd_Extended(int a, int b, int* x, int* y); // Function to find modulo inverse of a void Find_mod_Inverse(int a, int m) { int x, y; int g = Find_gcd_Extended(a, m, &x, &y); /* If the gcd value doesn't matches to 1, then inverse doesn't exist */ if (g != 1) { cout << "Inverse doesn't exist"; } else { /* m is added once more to handle negative values */ int res = (x % m + m) % m; cout<<res<<endl; } } // Function to find extended Euclidean Algorithm int Find_gcd_Extended(int a, int b, int* x, int* y) { // Base Case if (a == 0) { *x = 0, *y = 1; return b; } // Storing results of recursive call int x1, y1; int gcd = Find_gcd_Extended(b % a, a, &x1, &y1); /* After recursive call, update the values of x and y */ *x = y1 - (b / a) * x1; *y = x1; return gcd; } // Driver Code int main() { int a = 5, m = 7; // Function call cout<<"The value of x is: "; Find_mod_Inverse(a, m); return 0; } |
Output:
| The value of x is: 3 |
Time Complexity: O(log m)
The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.
Space complexity: O(1)
As constant space is used, the space complexity is O(1).
Iterative Approach using Extended Euclid’s Algorithm:
The idea is very similar as we applied for the recursive way of the modular multiplicative inverse. Just the difference lies in the implementation part, in the above example we applied a recursive approach, now we will be looking for the iterative approach.
Implementation in C++:
/*
|
Output:
| The value of x is: 3 |
Time Complexity: O(log m)
The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.
Space Complexity: O(1)
As constant space is used, the space complexity is O(1).
Also see, Euclid GCD Algorithm
III: Fermat’s little theorem approach:
This approach is based on Fermat’s little theorem. This approach can only work if m is prime.
Multiplying by a-1on both sides we get,
| /* C++ program for modular multiplicative inverse when m is prime */ #include <iostream> using namespace std; /* Function to find gcd of a and b */ int __gcd(int a, int b); /* Function for computing the expression x raised to power y under modulo m */ int find_power(int x, int y, int m); /* For prime m,this function finds modular inverse of a under modulo m */ void find_mod_Inverse(int a, int m) { int g = __gcd(a, m); if (g != 1) { cout << "Inverse doesn't exist"; } else { /* When a and m are prime, then modulo inverse can be defined as a^(m-2) mode m */ cout << "The value of x is: " << find_power(a, m - 2, m); } } /* Function to compute x^y under modulo m */ int find_power(int x, int y, int m) { if (y == 0) { return 1; } int p = find_power(x, y / 2, m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m; } // Function to return gcd of a and b int __gcd(int x, int y) { if (x == 0) { return y; } return __gcd(y % x, x); } // Driver code int main() { int a = 5, m = 7; // Function call find_mod_Inverse(a, m); return 0; } |
Output:
| The value of x is: 3 |
Time Complexity: O(log m)
The time complexity of this approach is O(log m) as for every recursive call we are reducing ‘a’ by continuously doing mod with b.
Space Complexity: O(1)
As constant space is used, space complexity for this approach is O(1).
Frequently Asked Questions:
What is the output of 3 mod 11?
The output of 3 mod 11 is 3.
What is an inverse?
The inverse is a way of representing a number in such a way that, when multiplied with its inverse, it gives 1 as result.
Eg: 5 X 1 / 5 = 1.
How do you do modular multiplicative inverse?
The modular multiplicative inverse is done by the “Chinese remainder theorem”. According to the Chinese remainder theorem, if one knows the remainder of the Euclidean division of an integer ’n’, then the remainder of the division of ‘n’ by the product of the integers can be uniquely determined under the condition that divisors are pairwise coprime
What is the easiest way to find a multiplicative inverse?
For any natural number x(0, 1, 2, 3, …), the multiplicative inverse is 1/x. For example, the multiplicative inverse of 7 is 1/7.
Key Takeaways:
In this article we learned about modular multiplicative inverse and various approaches to solving it, starting from the naive to efficient approach. But this isn’t the end.
Recommended Readings:
You can also try solving problems on Coding Ninjas Studio. If you think that this blog helped you, then share it with your friends!.
~ Pradipta Choudhury
