Modular multiplicative inverse
Given two integers A and M, find the modular multiplicative inverse of A under modulo M.
The modular multiplicative inverse is an integer X such that:
A X ? 1 (mod M)
Note: The value of X should be in the range {1, 2, … M-1}, i.e., in the range of integer modulo M. ( Note that X cannot be 0 as A*0 mod M will never be 1). The multiplicative inverse of “A modulo M” exists if and only if A and M are relatively prime (i.e. if gcd(A, M) = 1)
Examples:
Input: A = 3, M = 11
Output: 4
Explanation: Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(under 11).
One might think, 15 also as a valid output as “(15*3) mod 11”
is also 1, but 15 is not in range {1, 2, … 10}, so not valid.Input: A = 10, M = 17
Output: 12
Explamation: Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).
Naive Approach: To solve the problem, follow the below idea:
A naive method is to try all numbers from 1 to m. For every number x, check if (A * X) % M is 1
Below is the implementation of the above approach:
C++
// C++ program to find modular // inverse of A under modulo M #include <bits/stdc++.h> using namespace std; // A naive method to find modular // multiplicative inverse of 'A' // under modulo 'M' int modInverse( int A, int M) { for ( int X = 1; X < M; X++) if (((A % M) * (X % M)) % M == 1) return X; } // Driver code int main() { int A = 3, M = 11; // Function call cout << modInverse(A, M); return 0; } |
Java
// Java program to find modular inverse // of A under modulo M import java.io.*; class GFG { // A naive method to find modulor // multiplicative inverse of A // under modulo M static int modInverse( int A, int M) { for ( int X = 1 ; X < M; X++) if (((A % M) * (X % M)) % M == 1 ) return X; return 1 ; } // Driver Code public static void main(String args[]) { int A = 3 , M = 11 ; // Function call System.out.println(modInverse(A, M)); } } /*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python3 program to find modular # inverse of A under modulo M # A naive method to find modulor # multiplicative inverse of A # under modulo M def modInverse(A, M): for X in range ( 1 , M): if (((A % M) * (X % M)) % M = = 1 ): return X return - 1 # Driver Code if __name__ = = "__main__" : A = 3 M = 11 # Function call print (modInverse(A, M)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find modular inverse // of A under modulo M using System; class GFG { // A naive method to find modulor // multiplicative inverse of A // under modulo M static int modInverse( int A, int M) { for ( int X = 1; X < M; X++) if (((A % M) * (X % M)) % M == 1) return X; return 1; } // Driver Code public static void Main() { int A = 3, M = 11; // Function call Console.WriteLine(modInverse(A, M)); } } // This code is contributed by anuj_67. |
Javascript
<script> // Javascript program to find modular // inverse of a under modulo m // A naive method to find modulor // multiplicative inverse of // 'a' under modulo 'm' function modInverse(a, m) { for (let x = 1; x < m; x++) if (((a % m) * (x % m)) % m == 1) return x; } // Driver Code let a = 3; let m = 11; // Function call document.write(modInverse(a, m)); // This code is contributed by _saurabh_jaiswal. </script> |
PHP
<?php // PHP program to find modular // inverse of A under modulo M // A naive method to find modulor // multiplicative inverse of // A under modulo M function modInverse( $A , $M ) { for ( $X = 1; $X < $M ; $X ++) if ((( $A % $M ) * ( $X % $M )) % $M == 1) return $X ; } // Driver Code $A = 3; $M = 11; // Function call echo modInverse( $A , $M ); // This code is contributed by anuj_67. ?> |
4
Time Complexity: O(M)
Auxiliary Space: O(1)
Modular multiplicative inverse when M and A are coprime or gcd(A, M)=1:
The idea is to use Extended Euclidean algorithms that take two integers ‘a’ and ‘b’, then find their gcd, and also find ‘x’ and ‘y’ such that
ax + by = gcd(a, b)
To find the multiplicative inverse of ‘A’ under ‘M’, we put b = M in the above formula. Since we know that A and M are relatively prime, we can put the value of gcd as 1.
Ax + My = 1
If we take modulo M on both sides, we get
Ax + My ? 1 (mod M)
We can remove the second term on left side as ‘My (mod M)’ would always be 0 for an integer y.
Ax ? 1 (mod M)
So the ‘x’ that we can find using Extended Euclid Algorithm is the multiplicative inverse of ‘A’
Below is the implementation of the above approach:
C++
// C++ program to find multiplicative modulo // inverse using Extended Euclid algorithm. #include <bits/stdc++.h> using namespace std; // Function for extended Euclidean Algorithm int gcdExtended( int a, int b, int * x, int * y); // Function to find modulo inverse of a void modInverse( int A, int M) { int x, y; int g = gcdExtended(A, M, &x, &y); if (g != 1) cout << "Inverse doesn't exist" ; else { // m is added to handle negative x int res = (x % M + M) % M; cout << "Modular multiplicative inverse is " << res; } } // Function for extended Euclidean Algorithm int gcdExtended( int a, int b, int * x, int * y) { // Base Case if (a == 0) { *x = 0, *y = 1; return b; } // To store results of recursive call int x1, y1; int gcd = gcdExtended(b % a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b / a) * x1; *y = x1; return gcd; } // Driver Code int main() { int A = 3, M = 11; // Function call modInverse(A, M); return 0; } // This code is contributed by khushboogoyal499 |
C
// C program to find multiplicative modulo inverse using // Extended Euclid algorithm. #include <stdio.h> // C function for extended Euclidean Algorithm int gcdExtended( int a, int b, int * x, int * y); // Function to find modulo inverse of a void modInverse( int A, int M) { int x, y; int g = gcdExtended(A, M, &x, &y); if (g != 1) printf ( "Inverse doesn't exist" ); else { // m is added to handle negative x int res = (x % M + M) % M; printf ( "Modular multiplicative inverse is %d" , res); } } // C function for extended Euclidean Algorithm int gcdExtended( int a, int b, int * x, int * y) { // Base Case if (a == 0) { *x = 0, *y = 1; return b; } int x1, y1; // To store results of recursive call int gcd = gcdExtended(b % a, a, &x1, &y1); // Update x and y using results of recursive // call *x = y1 - (b / a) * x1; *y = x1; return gcd; } // Driver Code int main() { int A = 3, M = 11; // Function call modInverse(A, M); return 0; } |
Java
// java program to find multiplicative modulo // inverse using Extended Euclid algorithm. public class GFG { // Global Variables public static int x; public static int y; // Function for extended Euclidean Algorithm static int gcdExtended( int a, int b) { // Base Case if (a == 0 ) { x = 0 ; y = 1 ; return b; } // To store results of recursive call int gcd = gcdExtended(b % a, a); int x1 = x; int y1 = y; // Update x and y using results of recursive // call int tmp = b / a; x = y1 - tmp * x1; y = x1; return gcd; } static void modInverse( int A, int M) { int g = gcdExtended(A, M); if (g != 1 ) { System.out.println( "Inverse doesn't exist" ); } else { // m is added to handle negative x int res = (x % M + M) % M; System.out.println( "Modular multiplicative inverse is " + res); } } // Driver code public static void main(String[] args) { int A = 3 , M = 11 ; // Function Call modInverse(A, M); } } // The code is contributed by Gautam goel (gautamgoel962) |
Python3
# Python3 program to find multiplicative modulo # inverse using Extended Euclid algorithm. # Global Variables x, y = 0 , 1 # Function for extended Euclidean Algorithm def gcdExtended(a, b): global x, y # Base Case if (a = = 0 ): x = 0 y = 1 return b # To store results of recursive call gcd = gcdExtended(b % a, a) x1 = x y1 = y # Update x and y using results of recursive # call x = y1 - (b / / a) * x1 y = x1 return gcd def modInverse(A, M): g = gcdExtended(A, M) if (g ! = 1 ): print ( "Inverse doesn't exist" ) else : # m is added to handle negative x res = (x % M + M) % M print ( "Modular multiplicative inverse is " , res) # Driver Code if __name__ = = "__main__" : A = 3 M = 11 # Function call modInverse(A, M) # This code is contributed by phasing17 |
C#
// C# program to find multiplicative modulo // inverse using Extended Euclid algorithm. using System; public class GFG { public static int x, y; // Function for extended Euclidean Algorithm static int gcdExtended( int a, int b) { // Base Case if (a == 0) { x = 0; y = 1; return b; } // To store results of recursive call int gcd = gcdExtended(b % a, a); int x1 = x; int y1 = y; // Update x and y using results of recursive // call x = y1 - (b / a) * x1; y = x1; return gcd; } // Function to find modulo inverse of a static void modInverse( int A, int M) { int g = gcdExtended(A, M); if (g != 1) Console.Write( "Inverse doesn't exist" ); else { // M is added to handle negative x int res = (x % M + M) % M; Console.Write( "Modular multiplicative inverse is " + res); } } // Driver Code public static void Main( string [] args) { int A = 3, M = 11; // Function call modInverse(A, M); } } // this code is contributed by phasing17 |
Javascript
<script> // JavaScript program to find multiplicative modulo // inverse using Extended Euclid algorithm. // Global Variables let x, y; // Function for extended Euclidean Algorithm function gcdExtended(a, b){ // Base Case if (a == 0) { x = 0; y = 1; return b; } // To store results of recursive call let gcd = gcdExtended(b % a, a); let x1 = x; let y1 = y; // Update x and y using results of recursive // call x = y1 - Math.floor(b / a) * x1; y = x1; return gcd; } function modInverse(a, m) { let g = gcdExtended(a, m); if (g != 1){ document.write( "Inverse doesn't exist" ); } else { // m is added to handle negative x let res = (x % m + m) % m; document.write( "Modular multiplicative inverse is " , res); } } // Driver Code { let a = 3, m = 11; // Function call modInverse(a, m); } // This code is contributed by Gautam goel (gautamgoel962) </script> |
PHP
<?php // PHP program to find multiplicative modulo // inverse using Extended Euclid algorithm. // Function to find modulo inverse of a function modInverse( $A , $M ) { $x = 0; $y = 0; $g = gcdExtended( $A , $M , $x , $y ); if ( $g != 1) echo "Inverse doesn't exist" ; else { // m is added to handle negative x $res = ( $x % $M + $M ) % $M ; echo "Modular multiplicative " . "inverse is " . $res ; } } // function for extended Euclidean Algorithm function gcdExtended( $a , $b , & $x , & $y ) { // Base Case if ( $a == 0) { $x = 0; $y = 1; return $b ; } $x1 ; $y1 ; // To store results of recursive call $gcd = gcdExtended( $b % $a , $a , $x1 , $y1 ); // Update x and y using results of // recursive call $x = $y1 - (int)( $b / $a ) * $x1 ; $y = $x1 ; return $gcd ; } // Driver Code $A = 3; $M = 11; // Function call modInverse( $A , $M ); // This code is contributed by chandan_jnu ?> |
Modular multiplicative inverse is 4
Time Complexity: O(log M)
Auxiliary Space: O(log M), because of the internal recursion stack.
Iterative Implementation of the above approach:
C++
// Iterative C++ program to find modular // inverse using extended Euclid algorithm #include <bits/stdc++.h> using namespace std; // Returns modulo inverse of a with respect // to m using extended Euclid Algorithm // Assumption: a and m are coprimes, i.e., // gcd(A, M) = 1 int modInverse( int A, int M) { int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process same as // Euclid's algo M = A % M, A = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // Driver Code int main() { int A = 3, M = 11; // Function call cout << "Modular multiplicative inverse is " << modInverse(A, M); return 0; } // this code is contributed by shivanisinghss2110 |
C
// Iterative C program to find modular // inverse using extended Euclid algorithm #include <stdio.h> // Returns modulo inverse of a with respect // to m using extended Euclid Algorithm // Assumption: a and m are coprimes, i.e., // gcd(A, M) = 1 int modInverse( int A, int M) { int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process same as // Euclid's algo M = A % M, A = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // Driver Code int main() { int A = 3, M = 11; // Function call printf ( "Modular multiplicative inverse is %d\n" , modInverse(A, M)); return 0; } |
Java
// Iterative Java program to find modular // inverse using extended Euclid algorithm class GFG { // Returns modulo inverse of a with // respect to m using extended Euclid // Algorithm Assumption: a and m are // coprimes, i.e., gcd(A, M) = 1 static int modInverse( int A, int M) { int m0 = M; int y = 0 , x = 1 ; if (M == 1 ) return 0 ; while (A > 1 ) { // q is quotient int q = A / M; int t = M; // m is remainder now, process // same as Euclid's algo M = A % M; A = t; t = y; // Update x and y y = x - q * y; x = t; } // Make x positive if (x < 0 ) x += m0; return x; } // Driver code public static void main(String args[]) { int A = 3 , M = 11 ; // Function call System.out.println( "Modular multiplicative " + "inverse is " + modInverse(A, M)); } } /*This code is contributed by Nikita Tiwari.*/ |
Python3
# Iterative Python 3 program to find # modular inverse using extended # Euclid algorithm # Returns modulo inverse of a with # respect to m using extended Euclid # Algorithm Assumption: a and m are # coprimes, i.e., gcd(A, M) = 1 def modInverse(A, M): m0 = M y = 0 x = 1 if (M = = 1 ): return 0 while (A > 1 ): # q is quotient q = A / / M t = M # m is remainder now, process # same as Euclid's algo M = A % M A = t t = y # Update x and y y = x - q * y x = t # Make x positive if (x < 0 ): x = x + m0 return x # Driver code if __name__ = = "__main__" : A = 3 M = 11 # Function call print ( "Modular multiplicative inverse is" , modInverse(A, M)) # This code is contributed by Nikita tiwari. |
C#
// Iterative C# program to find modular // inverse using extended Euclid algorithm using System; class GFG { // Returns modulo inverse of a with // respect to m using extended Euclid // Algorithm Assumption: a and m are // coprimes, i.e., gcd(A, M) = 1 static int modInverse( int A, int M) { int m0 = M; int y = 0, x = 1; if (M == 1) return 0; while (A > 1) { // q is quotient int q = A / M; int t = M; // m is remainder now, process // same as Euclid's algo M = A % M; A = t; t = y; // Update x and y y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // Driver Code public static void Main() { int A = 3, M = 11; // Function call Console.WriteLine( "Modular multiplicative " + "inverse is " + modInverse(A, M)); } } // This code is contributed by anuj_67. |
Javascript
<script> // Iterative Javascript program to find modular // inverse using extended Euclid algorithm // Returns modulo inverse of a with respect // to m using extended Euclid Algorithm // Assumption: a and m are coprimes, i.e., // gcd(a, m) = 1 function modInverse(a, m) { let m0 = m; let y = 0; let x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient let q = parseInt(a / m); let t = m; // m is remainder now, // process same as // Euclid's algo m = a % m; a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } // Driver Code let a = 3; let m = 11; // Function call document.write(`Modular multiplicative inverse is ${modInverse(a, m)}`); // This code is contributed by _saurabh_jaiswal </script> |
PHP
<?php // Iterative PHP program to find modular // inverse using extended Euclid algorithm // Returns modulo inverse of a with respect // to m using extended Euclid Algorithm // Assumption: a and m are coprimes, i.e., // gcd(a, m) = 1 function modInverse( $A , $M ) { $m0 = $M ; $y = 0; $x = 1; if ( $m == 1) return 0; while ( $A > 1) { // q is quotient $q = (int) ( $A / $M ); $t = $M ; // m is remainder now, // process same as // Euclid's algo $M = $A % $M ; $A = $t ; $t = $y ; // Update y and x $y = $x - $q * $y ; $x = $t ; } // Make x positive if ( $x < 0) $x += $m0 ; return $x ; } // Driver Code $A = 3; $M = 11; // Function call echo "Modular multiplicative inverse is: " , modInverse( $A , $M ); // This code is contributed by Anuj_67 ?> |
Modular multiplicative inverse is 4
Time Complexity: O(log m)
Auxiliary Space: O(1)
Modular multiplicative inverse when M is prime:
If we know M is prime, then we can also use Fermat’s little theorem to find the inverse.
aM-1 ? 1 (mod M)
If we multiply both sides with a-1, we get
a-1 ? a M-2 (mod M)
Below is the implementation of the above approach:
C++
// C++ program to find modular inverse of A under modulo M // This program works only if M is prime. #include <bits/stdc++.h> using namespace std; // To find GCD of a and b int gcd( int a, int b); // To compute x raised to power y under modulo M int power( int x, unsigned int y, unsigned int M); // Function to find modular inverse of a under modulo M // Assumption: M is prime void modInverse( int A, int M) { int g = gcd(A, M); if (g != 1) cout << "Inverse doesn't exist" ; else { // If a and m are relatively prime, then modulo // inverse is a^(m-2) mode m cout << "Modular multiplicative inverse is " << power(A, M - 2, M); } } // To compute x^y under modulo m int power( int x, unsigned int y, unsigned int M) { if (y == 0) return 1; int p = 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 a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Driver code int main() { int A = 3, M = 11; // Function call modInverse(A, M); return 0; } |
Java
// Java program to find modular // inverse of A under modulo M // This program works only if // M is prime. import java.io.*; class GFG { // Function to find modular inverse of a // under modulo M Assumption: M is prime static void modInverse( int A, int M) { int g = gcd(A, M); if (g != 1 ) System.out.println( "Inverse doesn't exist" ); else { // If a and m are relatively prime, then modulo // inverse is a^(m-2) mode m System.out.println( "Modular multiplicative inverse is " + power(A, M - 2 , M)); } } static int power( int x, int y, int M) { if (y == 0 ) return 1 ; int p = power(x, y / 2 , M) % M; p = ( int )((p * ( long )p) % M); if (y % 2 == 0 ) return p; else return ( int )((x * ( long )p) % M); } // Function to return gcd of a and b static int gcd( int a, int b) { if (a == 0 ) return b; return gcd(b % a, a); } // Driver Code public static void main(String args[]) { int A = 3 , M = 11 ; // Function call modInverse(A, M); } } // This code is contributed by Nikita Tiwari. |
Python3
# Python3 program to find modular # inverse of A under modulo M # This program works only if M is prime. # Function to find modular # inverse of A under modulo M # Assumption: M is prime def modInverse(A, M): g = gcd(A, M) if (g ! = 1 ): print ( "Inverse doesn't exist" ) else : # If A and M are relatively prime, # then modulo inverse is A^(M-2) mod M print ( "Modular multiplicative inverse is " , power(A, M - 2 , M)) # To compute x^y under modulo M def power(x, y, M): if (y = = 0 ): return 1 p = power(x, y / / 2 , M) % M p = (p * p) % M if (y % 2 = = 0 ): return p else : return ((x * p) % M) # Function to return gcd of a and b def gcd(a, b): if (a = = 0 ): return b return gcd(b % a, a) # Driver Code if __name__ = = "__main__" : A = 3 M = 11 # Function call modInverse(A, M) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find modular // inverse of a under modulo M // This program works only if // M is prime. using System; class GFG { // Function to find modular // inverse of A under modulo // M Assumption: M is prime static void modInverse( int A, int M) { int g = gcd(A, M); if (g != 1) Console.Write( "Inverse doesn't exist" ); else { // If A and M are relatively // prime, then modulo inverse // is A^(M-2) mod M Console.Write( "Modular multiplicative inverse is " + power(A, M - 2, M)); } } // To compute x^y under // modulo M static int power( int x, int y, int M) { if (y == 0) return 1; int p = power(x, y / 2, M) % M; p = (p * p) % M; if (y % 2 == 0) return p; else return (x * p) % M; } // Function to return // gcd of a and b static int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Driver Code public static void Main() { int A = 3, M = 11; // Function call modInverse(A, M); } } // This code is contributed by nitin mittal. |
Javascript
<script> // Javascript program to find modular inverse of a under modulo m // This program works only if m is prime. // Function to find modular inverse of a under modulo m // Assumption: m is prime function modInverse(a, m) { let g = gcd(a, m); if (g != 1) document.write( "Inverse doesn't exist" ); else { // If a and m are relatively prime, then modulo // inverse is a^(m-2) mode m document.write( "Modular multiplicative inverse is " + power(a, m - 2, m)); } } // To compute x^y under modulo m function power(x, y, m) { if (y == 0) return 1; let p = power(x, parseInt(y / 2), m) % m; p = (p * p) % m; return (y % 2 == 0) ? p : (x * p) % m; } // Function to return gcd of a and b function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); } // Driver code let a = 3, m = 11; // Function call modInverse(a, m); // This code is contributed by subham348. </script> |
PHP
<?php // PHP program to find modular // inverse of A under modulo M // This program works only if M // is prime. // Function to find modular // inverse of A under modulo // M Assumption: M is prime function modInverse( $A , $M ) { $g = gcd( $A , $M ); if ( $g != 1) echo "Inverse doesn't exist" ; else { // If A and M are relatively // prime, then modulo inverse // is A^(M-2) mod M echo "Modular multiplicative inverse is " , power( $A , $M - 2, $M ); } } // To compute x^y under modulo m function power( $x , $y , $M ) { if ( $y == 0) return 1; $p = 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 function gcd( $a , $b ) { if ( $a == 0) return $b ; return gcd( $b % $a , $a ); } // Driver Code $A = 3; $M = 11; // Function call modInverse( $A , $M ); // This code is contributed by anuj_67. ?> |
Modular multiplicative inverse is 4
Time Complexity: O(log M)
Auxiliary Space: O(log M), because of the internal recursion stack.
Applications:
Computation of the modular multiplicative inverse is an essential step in RSA public-key encryption method.
This article is contributed by Ankur.