Calcule o inverso multiplicativo modular em Python
- Modular Multiplicativo Inverso Usando a Abordagem Ingênua Iterativa
-
Modular Multiplicativo Inverso Usando Função Integrada
pow()
Se tivermos dois números a e m, então o inverso multiplicativo modular de a é x no módulo m se:
a * x % m = 1
Neste caso, o inverso multiplicativo existe apenas se a e m forem relativamente primos, ou seja, se o maior divisor comum de a e m for 1.
O valor de x pode variar de 1 a m-1.
Modular Multiplicativo Inverso Usando a Abordagem Ingênua Iterativa
Suponha que precisamos encontrar o inverso multiplicativo de a no módulo m. Se o inverso do módulo multiplicativo existe, seu valor pode variar de 1 a m-1. Portanto, iteramos por esse intervalo e verificamos a condição para o inverso do módulo multiplicativo. Se qualquer número dentro do intervalo satisfizer a condição, temos o número como módulo multiplicativo inverso.
def find_mod_inv(a,m):
for x in range(1,m):
if((a%m)*(x%m) % m==1):
return x
raise Exception('The modular inverse does not exist.')
a = 13
m = 22
try:
res=find_mod_inv(a,m)
print("The required modular inverse is: "+ str(res))
except:
print('The modular inverse does not exist.')
Produção:
The required modular inverse is: 17
Aqui, temos uma função chamada find_mod_inv que leva a e m como entrada e retorna o inverso multiplicativo de a no módulo m.
Se o número a não tiver um inverso multiplicativo de a no módulo m, ele aumentará e exceção.
No exemplo acima, podemos ver o inverso multiplicativo modular de 13 no módulo 22 é 17.
Modular Multiplicativo Inverso Usando Função Integrada pow()
Também podemos usar a função integrada pow() do Python para calcular o inverso multiplicativo modular de um número.
a=38
m=97
res = pow(a, m-2, m)
print("The required modular inverse is: "+ str(res))
Produção:
The required modular inverse is: 23
Para calcular o módulo multiplicativo inverso usando o método pow(), o primeiro parâmetro para o método pow() será o número cujo módulo inverso deve ser encontrado, o segundo parâmetro será a ordem do módulo subtraído por 2 e o último parâmetro será a ordem do módulo.
No entanto, para Python 3.8 e superior, podemos substituir o segundo argumento por -1.
a=38
m=97
res = pow(a, -1, m)
print("The required modular inverse is: "+ str(res))
saída
The required modular inverse is: 23
