Calcule o inverso multiplicativo modular em Python

1. Modular Multiplicativo Inverso Usando a Abordagem Ingênua Iterativa
2. 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