# 算法设计：模乘逆元问题

2021年3月17日14:40:14 发表评论 620 次浏览

## 本文概述

``a x  ≡ 1 (mod m)``

x的值应为{0, 1, 2, …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).``````

## 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``

``ax + by = gcd(a, b)``

``ax + my = 1``

``ax + my ≡ 1 (mod m)``

``ax  ≡ 1 (mod m)``

## 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 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 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 = 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 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``

``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 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 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``

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

。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。