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