本文概述
给定两个整数" 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 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
该方法的时间复杂度为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 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
该方法的时间复杂度为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
本文作者:
安库尔
。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。