Calcular el inverso multiplicativo modular en Python

1. Inverso multiplicativo modular utilizando el enfoque iterativo ingenuo
2. Inverso multiplicativo modular usando la función incorporada pow()

Si tenemos dos números a y m, entonces el inverso multiplicativo modular de a es x bajo módulo m si:

a * x % m = 1

En este caso, el inverso multiplicativo existe sólo si a y m son primos relativos, es decir, si el máximo común divisor de a y m es 1.

El valor de x puede oscilar entre 1 y m-1.

Inverso multiplicativo modular utilizando el enfoque iterativo ingenuo

Suponga que necesitamos encontrar el inverso multiplicativo de a bajo módulo m. Si existe el inverso módulo multiplicativo, su valor puede oscilar entre 1 y m-1. Por lo tanto, iteramos a través de este rango y verificamos la condición para el inverso módulo multiplicativo. Si cualquier número dentro del rango satisface la condición, tenemos el número como módulo inverso multiplicativo.

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.")

Producción :

The required modular inverse is: 17

Aquí, tenemos una función llamada find_mod_inv que toma a y m como entrada y devuelve el inverso multiplicativo de a bajo módulo m.

Si el número a no tiene un inverso multiplicativo de a en el módulo m, se generará una excepción.

En el ejemplo anterior, podemos ver que el inverso multiplicativo modular de 13 en el módulo 22 es 17.

Inverso multiplicativo modular usando la función incorporada pow()

También podemos usar la función incorporada pow() de Python para calcular el inverso multiplicativo modular de un número.

a = 38
m = 97
res = pow(a, m - 2, m)
print("The required modular inverse is: " + str(res))

Producción :

The required modular inverse is: 23

Para calcular el inverso módulo multiplicativo utilizando el método pow(), el primer parámetro del método pow() será el número cuyo módulo inverso se va a encontrar, el segundo parámetro será el orden del módulo restado por 2 y el último parámetro será el orden de módulo.

Sin embargo, para Python 3.8 y superior, podemos reemplazar el segundo argumento con -1.

a = 38
m = 97
res = pow(a, -1, m)
print("The required modular inverse is: " + str(res))

Producción :

The required modular inverse is: 23