本文概述给定两个整数" a"和" m", 在模" m"下找到" a"的模乘逆。
模乘法逆是一个整数" x", 使得。

a x≡ 1 (mod m)

x的值应为{0, 1, 2, …m-1}, 即在整数模m的范围内。
当且仅当a和m相对质数(即gcd(a, m)= 1)时, 才存在"模m"的乘法逆。
例子：

Input:a = 3, m = 11 Output: 4 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 ring {0, 1, 2, ... 10}, so not valid.Input:a = 10, m = 17 Output: 12 Since (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) { a = a%m; for ( int x=1; x< m; x++) if ((a*x) % m == 1) return x; }// Driver Program int main() { int a = 3, m = 11; 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) { a = a % m; for ( int x = 1 ; x < m; x++) if ((a * x) % m == 1 ) return x; return 1 ; }// Driver Program public static void main(String args[]) { int a = 3 , m = 11 ; System.out.println(modInverse(a, m)); } }/*This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 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) : a = a % m; for x in range ( 1 , m) : if ((a * x) % m = = 1 ) : return x return 1# Driver Program a = 3 m = 11 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) { a = a % m; for ( int x = 1; x < m; x++) if ((a * x) % m == 1) return x; return 1; }// Driver Code public static void Main() { int a = 3, m = 11; 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 ) { $a = $a % $m ; for ( $x = 1; $x < $m ; $x ++) if (( $a * $x ) % $m == 1) return $x ; }// Driver Code $a = 3; $m = 11; echo modInverse( $a , $m ); // This code is contributed by anuj_67. ?>

输出如下：

4

该方法的时间复杂度为O(m)。
方法2(当m和a为互质时有效)
这个想法是使用
扩展的欧几里得算法
取两个整数" a"和" b", 找到它们的gcd并找到" x"和" y", 使得

ax + by = gcd(a, b)

要在" m"下找到" a"的乘法逆, 我们将b = m放在上式中。由于我们知道a和m是相对质数, 因此可以将gcd的值设为1。

ax + my = 1

如果我们在两边取模m, 我们得到

ax + my ≡ 1 (mod m)

我们可以删除左侧的第二项, 因为" my(mod m)"对于整数y始终为0。

ax≡ 1 (mod m)

因此, 我们可以找到的" x"
扩展欧几里得算法
是" a"的乘法逆
下面是上述算法的C ++实现。
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 Program int main() { int a = 3, m = 11; 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; modInverse( $a , $m ); // This code is contributed by chandan_jnu ?>

输出如下： 

Modular multiplicative inverse is 4

迭代实现：
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 program to test above function int main() { int a = 3, m = 11; printf ( "Modular multiplicative inverse is %d\n" , modInverse(a, m)); return 0; }

Java

// Iterative Java program to find modular // inverse using extended Euclid algorithmclass 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 program to test above function public static void main(String args[]) { int a = 3 , m = 11 ; 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 = 1if (m = = 1 ) : return 0while (a > 1 ) :# q is quotient q = a / / mt = 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 + m0return x# Driver program to test above function a = 3 m = 11 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; 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; echo "Modular multiplicative inverse is\n" , modInverse( $a , $m ); // This code is contributed by Anuj_67 ?>

输出如下：

Modular multiplicative inverse is 4

【算法设计（模乘逆元问题）】该方法的时间复杂度为O(Log m)
方法3(当m为素数时有效)
如果我们知道m是素数, 那么我们也可以使用
费马斯的小定理
寻找逆。

am-1 ≡ 1 (mod m)

如果我们将两边都乘以
-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 Program int main() { int a = 3, m = 11; 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)); } }// 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 Program public static void main(String args[]) { int a = 3 , m = 11 ; 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 1p = power(x, y / / 2 , m) % m p = (p * p) % mif (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 breturn gcd(b % a, a)# Driver Program a = 3 ; m = 11 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; 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; modInverse( $a , $m ); // This code is contributed by anuj_67. ?>

输出：

Modular multiplicative inverse is 4

该方法的时间复杂度为O(Log m)
我们讨论了三种找到乘法逆模m的方法。
1)天真的方法, O(m)
2)扩展的Euler GCD算法O(Log m)[当a和m为互素时有效]
3)费马小定理, O(Log m)[当'm'为素数时有效]
应用范围：
模乘法逆的计算是
RSA公钥加密方法
.
参考文献：
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
http://e-maxx.ru/algo/reverse_element
本文作者：
安库尔
。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  咸阳装修公司口碑最好 咸阳装修
• 

  风流果树种植方法，风流果种植栽培技术
• 

  恋爱中常吃醋的人有哪些表现 恋爱中的人为什么都容易吃醋
• 

  病人|如果你是卒中病人，如果你有这些不良习惯和错误观念……
• 

  尿蛋白1十需要治疗吗 尿蛋白高是怎么回事
• 

  牛油果能去火吗 吃牛油果去火吗
• 

  按摩八髎有什么作用
• 

  mysql几种连接方式 mysql怎么建立链接
• 

  英雄联盟9.16版本,潘森重做上线,技能逆天,网友：妥妥的上单霸主,如何评价？
• 

  vlan划分的目的是什么 为什么要划分vlan
• 

  涂防冻液只能冬天给车用吗,蚂蚁庄园防冻液12月25日答案
• 

  卫生统计数据分析报告,机构能源消耗统计数据分析报告
• 

  怀孕5个月了，能不能吃鸭血啊
• 

  2023年宁波九龙湖半程马拉松报名指南 2021宁波九龙湖马拉松报名
• 

  watchout,look out
• 

  佳能墨盒芯片怎么清零的-佳能打印机ip3680墨水计数怎么清零，要详细
• 

  自制葡萄酒的正确做法 自制葡萄酒怎么做
• 

  mysql数据库字段类型有哪些 mysql常用字段名
• 

  哪里有比较好用的pdf编辑器？
• 

  实验小学,附属小学,普通小学,有什么区别,都是什么意思？

• HTML DOM console.trace()方法用法实例
• 算法设计（多数元素问题）
• Python MongoDB – create_index查询用法详细示例
• 8085程序查找8位数字的平方
• PHP SplObjectStorage contains()函数用法详细介绍
• PHP date_default_timezone_get()函数用法介绍
• JavaScript基本语法指南（注释用法实例）
• U盘做系统,本文教您U盘做系统办法
• 笔记本u盘打开,本文教您联想笔记本u盘打开的办法