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 bint gcd(int a, int b);// To compute x raised to power y under modulo Mint power(int x, unsigned int y, unsigned int M);// Function to find modular inverse of a under modulo M// Assumption: M is primevoid 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 mint 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 bint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Driver codeint 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 primedef 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 Mdef 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 bdef gcd(a, b): if (a == 0): return b return gcd(b % a, a)# Driver Codeif __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 primefunction 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 mfunction 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 bfunction gcd(a, b){ if (a == 0) return b; return gcd(b % a, a);}// Driver codelet a = 3, m = 11;// Function callmodInverse(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 primefunction 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 mfunction 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 bfunction gcd($a, $b){ if ($a == 0) return $b; return gcd($b % $a, $a);}// Driver Code$A = 3;$M = 11;// Function callmodInverse($A, $M); // This code is contributed by anuj_67.?> |
Output
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.
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 codeint 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 Mimport 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 Mdef modInverse(A, M): for X in range(1, M): if (((A % M) * (X % M)) % M == 1): return X return -1# Driver Codeif __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 Musing 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 Codelet a = 3; let m = 11;// Function calldocument.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 Mfunction 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 callecho modInverse($A, $M);// This code is contributed by anuj_67.?> |
Output
4
Time Complexity: O(M)
Auxiliary Space: O(1)