本文概述给定两个整数" 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
本文作者：
安库尔
。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- HTML DOM console.trace()方法用法实例
- 算法设计（多数元素问题）
- Python MongoDB – create_index查询用法详细示例
- 8085程序查找8位数字的平方
- PHP SplObjectStorage contains()函数用法详细介绍
- PHP date_default_timezone_get()函数用法介绍
- JavaScript基本语法指南（注释用法实例）
- U盘做系统,本文教您U盘做系统办法
- 笔记本u盘打开,本文教您联想笔记本u盘打开的办法