Dados dos enteros ‘a’ y ‘m ‘, encuentra el inverso multiplicativo modular de ‘a’ bajo el módulo ‘m’ .
El inverso multiplicativo modular es un entero ‘x’ tal que.
a x ≅ 1 (mod m)
El valor de x debe estar en { 1, 2, … m-1}, es decir, en el rango de módulo entero m . (Tenga en cuenta que x no puede ser 0 ya que a*0 mod m nunca será 1 )
El inverso multiplicativo de “a módulo m” existe si y solo si a y m son primos relativos (es decir, si mcd(a, m) = 1 ).
Ejemplos:
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 {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).
Método 1 (Ingenuo)
Un método Ingenuo consiste en probar todos los números del 1 al m. Para cada número x, comprueba si (a*x)%m es 1.
A continuación se muestra la implementación de este método.
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>
Producción
4
Complejidad del tiempo: O(m)
Espacio Auxiliar: O(1)
Método 2 (Funciona cuando m y a son coprimos o mcd(a,m)=1)
La idea es usar algoritmos de Euclides extendidos que toman dos enteros ‘a’ y ‘b’, encuentran su mcd y también encuentran ‘x’ y ‘y’ tal que
ax + by = gcd(a, b)
Para encontrar el inverso multiplicativo de ‘a’ debajo de ‘m’, ponemos b = m en la fórmula anterior. Como sabemos que a y m son primos relativos, podemos poner el valor de gcd como 1.
ax + my = 1
Si tomamos módulo m en ambos lados, obtenemos
ax + my ≅ 1 (mod m)
Podemos eliminar el segundo término del lado izquierdo ya que ‘mi (mod m)’ siempre sería 0 para un número entero y.
ax ≅ 1 (mod m)
Entonces, la ‘x’ que podemos encontrar usando el Algoritmo de Euclides Extendido es el inverso multiplicativo de ‘a’
A continuación se muestra la implementación del algoritmo anterior.
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;
}
Java
// java program to find multiplicative modulo
// inverse using Extended Euclid algorithm.
public class GFG {
// Global Variables
public static int x;
public static int y;
// Function for extended Euclidean Algorithm
static int gcdExtended(int a,int b){
// Base Case
if (a == 0){
x = 0;
y = 1;
return b;
}
// To store results of recursive call
int gcd = gcdExtended(b % a, a);
int x1 = x;
int y1 = y;
// Update x and y using results of recursive
// call
int tmp = b/a;
x = y1 - tmp * x1;
y = x1;
return gcd;
}
static void modInverse(int a,int m){
int g = gcdExtended(a, m);
if (g != 1){
System.out.println("Inverse doesn't exist");
}
else
{
// m is added to handle negative x
int res = (x % m + m) % m;
System.out.println("Modular multiplicative inverse is " + res);
}
}
// Driver code
public static void main(String[] args) {
int a = 3, m = 11;
// Function Call
modInverse(a, m);
}
}
// The code is contributed by Gautam goel (gautamgoel962)
Python3
# Python3 program to find multiplicative modulo
# inverse using Extended Euclid algorithm.
# Global Variables
x, y = 0, 1
# Function for extended Euclidean Algorithm
def gcdExtended(a, b):
global x, y
# Base Case
if (a == 0):
x = 0
y = 1
return b
# To store results of recursive call
gcd = gcdExtended(b % a, a)
x1 = x
y1 = y
# Update x and y using results of recursive
# call
x = y1 - (b // a) * x1
y = x1
return gcd
def modInverse(a, m):
g = gcdExtended(a, m)
if (g != 1):
print("Inverse doesn't exist")
else:
# m is added to handle negative x
res = (x % m + m) % m
print("Modular multiplicative inverse is ", res)
# Driver Code
a = 3
m = 11
# Function call
modInverse(a, m)
# This code is contributed by phasing17
C#
// C# program to find multiplicative modulo
// inverse using Extended Euclid algorithm.
using System;
public class GFG
{
public static int x, y;
// Function for extended Euclidean Algorithm
static int gcdExtended(int a, int b)
{
// Base Case
if (a == 0)
{
x = 0;
y = 1;
return b;
}
// To store results of recursive call
int gcd = gcdExtended(b % a, a);
int x1 = x;
int y1 = y;
// Update x and y using results of recursive
// call
x = y1 - (b / a) * x1;
y = x1;
return gcd;
}
// Function to find modulo inverse of a
static void modInverse(int a, int m)
{
int g = gcdExtended(a, m);
if (g != 1)
Console.Write("Inverse doesn't exist");
else
{
// m is added to handle negative x
int res = (x % m + m) % m;
Console.Write("Modular multiplicative inverse is " + res);
}
}
//Driver Code
public static void Main(string[] args)
{
int a = 3, m = 11;
// Function call
modInverse(a, m);
}
}
//this code is contributed by phasing17
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
≅>
Javascript
<script>
// JavaScript program to find multiplicative modulo
// inverse using Extended Euclid algorithm.
// Global Variables
let x, y;
// Function for extended Euclidean Algorithm
function gcdExtended(a, b){
// Base Case
if (a == 0)
{
x = 0;
y = 1;
return b;
}
// To store results of recursive call
let gcd = gcdExtended(b % a, a);
let x1 = x;
let y1 = y;
// Update x and y using results of recursive
// call
x = y1 - Math.floor(b / a) * x1;
y = x1;
return gcd;
}
function modInverse(a, m)
{
let g = gcdExtended(a, m);
if (g != 1){
document.write("Inverse doesn't exist");
}
else{
// m is added to handle negative x
let res = (x % m + m) % m;
document.write("Modular multiplicative inverse is ", res);
}
}
// Driver Code
{
let a = 3, m = 11;
// Function call
modInverse(a, m);
}
// This code is contributed by Gautam goel (gautamgoel962)
</script>
Producción
Modular multiplicative inverse is 4
Complejidad del tiempo: O(log m)
Espacio auxiliar: O(log m) debido a la pila de recursión interna.
Implementación iterativa:
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\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 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\n",
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>
Producción
Modular multiplicative inverse is 4
Complejidad del tiempo: O(log m)
Espacio Auxiliar: O(1)
Método 3 (Funciona cuando m es primo)
Si sabemos que m es primo, también podemos usar el pequeño teorema de Fermats para encontrar el inverso.
am-1 ≅ 1 (mod m)
Si multiplicamos ambos lados por -1 , obtenemos
a-1 ≅ a m-2 (mod m)
A continuación se muestra la implementación de la idea anterior.
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>
Producción
Modular multiplicative inverse is 4
Complejidad del tiempo: O(log m)
Espacio auxiliar: O(log m) debido a la pila de recursión interna.
Hemos discutido tres métodos para encontrar el módulo inverso multiplicativo m.
1) Método ingenuo, O(m)
2) Algoritmo GCD de Euler extendido, O(Log m) [Funciona cuando a y m son coprimos]
3) Pequeño teorema de Fermat, O(Log m) [Funciona cuando ‘m’ es primo]
Aplicaciones:
El cálculo del inverso multiplicativo modular es un paso esencial en el método de cifrado de clave pública RSA .
Referencias:
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
http://e-maxx.ru/algo/reverse_element
Este artículo es una contribución de Ankur . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA