Calculer l'inverse multiplicatif modulaire en Python

1. Inverse multiplicative modulaire utilisant l’approche itérative naïve
2. Inverse multiplicative modulaire utilisant la fonction intégrée pow()

Si nous avons deux nombres a et m, alors l’inverse multiplicatif modulaire de a est x sous modulo m si :

a * x % m = 1

Dans ce cas, l’inverse multiplicatif n’existe que si a et m sont relativement premiers, c’est-à-dire si le plus grand diviseur commun de a et de m est 1.

La valeur de x peut aller de 1 à m-1.

Inverse multiplicative modulaire utilisant l’approche itérative naïve

Supposons que nous ayons besoin de trouver l’inverse multiplicatif de a sous modulo m. Si l’inverse multiplicatif modulo existe, sa valeur peut aller de 1 à m-1. Par conséquent, nous parcourons cette plage et vérifions la condition de l’inverse multiplicatif modulo. Si un nombre dans la plage satisfait la condition, nous avons le nombre comme inverse multiplicatif modulo.

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

Production:

The required modular inverse is: 17

Ici, nous avons une fonction nommée find_mod_inv qui prend a et m en entrée et renvoie l’inverse multiplicatif de a sous modulo m.

Si le nombre a n’a pas d’inverse multiplicatif de a sous modulo m, il lèvera une exception.

À partir de l’exemple ci-dessus, nous pouvons voir que l’inverse multiplicatif modulaire de 13 sous modulo 22 est 17.

Inverse multiplicative modulaire utilisant la fonction intégrée pow()

Nous pouvons également utiliser la fonction intégrée pow() de Python pour calculer l’inverse multiplicatif modulaire d’un nombre.

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

Production:

The required modular inverse is: 23

Pour calculer l’inverse multiplicatif modulo à l’aide de la méthode pow(), le premier paramètre de la méthode pow() sera le nombre dont on cherche l’inverse modulo, le deuxième paramètre sera l’ordre de modulo soustrait par 2 et le dernier paramètre sera l’ordre de modulo.

Cependant, pour Python 3.8 et au-dessus, nous pouvons remplacer le deuxième argument par -1.

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

Production:

The required modular inverse is: 23