给定两个整数 “a” 和 “嗯 ，求的模乘逆 “a” 模下 我是 . 模乘逆是一个整数 “x” 这样。
null
a x ≅ 1 (mod m)
价值 十、 应该在{1,2 M （注意 十、 不可能 0 像 a*0 mod m 永远不会 1. ) 当且仅当a和m是相对素数时（即当gcd（a，m）=1），存在“a模m”的乘法逆。
例如：
Input: a = 3, m = 11Output: 4Since (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 ring {1, 2, ... 10}, so not valid.Input: a = 10, m = 17Output: 12Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).
方法1（天真） 一个简单的方法是尝试从1到m的所有数字。对于每个数字x，检查（A*x）%m是否为1。
下面是这个方法的实现。
C++
// C++ program to find modular // inverse of a under modulo m #include <iostream> 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 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. |
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. ≅> |
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> |
输出
4
时间复杂性： O（m）
辅助空间： O（1）
方法2（当m和a是互质或gcd（a，m）=1时有效） 这个想法是使用 扩展欧几里德算法 取两个整数“a”和“b”，找到它们的 gcd 还有找到 “x” 和 “是的” 以至于
ax + by = gcd(a, b)
为了求‘m’下‘a’的乘法逆，我们把b=m放在上面的公式中。因为我们知道a和m是相对素数，所以我们可以把gcd的值设为1。
ax + my = 1
如果两边都取模m，我们得到
ax + my ≅ 1 (mod m)
我们可以去掉左边的第二项，因为对于整数y，“my（mod m）”总是0。
ax ≅ 1 (mod m)
所以我们可以用 扩展欧几里德算法 是“a”的乘法逆
下面是上述算法的实现。
C++
// C++ program to find multiplicative modulo // inverse using Extended Euclid algorithm. #include <iostream> 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; } |
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
时间复杂性： O（对数m）
辅助空间： O（logm），因为内部递归堆栈。
迭代实现：
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" , 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 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. |
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 ≅> |
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> |
输出
Modular multiplicative inverse is 4
时间复杂性： O（对数m）
辅助空间： O（1）
方法3（m为素数时有效） 如果我们知道m是素数，那么我们也可以使用 费马茨小定理 找到相反的结果。
am-1 ≅ 1 (mod m)
如果我们用a乘两边 -1 ，我们得到
a-1 ≅ a m-2 (mod m)
下面是上述想法的实施。
C++
// C++ program to find modular inverse of a under modulo m // This program works only if m is prime. #include <iostream> 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) mode 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 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) mode 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. |
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) mode 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. ≅> |
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> |
输出
Modular multiplicative inverse is 4
时间复杂性： O（对数m）
辅助空间： O（logm），因为内部递归堆栈。
我们讨论了求乘法逆模m的三种方法。 1） 朴素的方法，O（m） 2） 扩展的Euler的GCD算法O（logm）[当a和m是互质时有效] 3） 费马的小定理O（logm）[当’m’是素数时有效]
应用： 模乘法逆的计算是数学中的一个重要步骤 RSA公钥加密方法 .
参考资料： https://en.wikipedia.org/wiki/Modular_multiplicative_inverse http://e-maxx.ru/algo/reverse_element 本文由 安克尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
