Fonction inverse multiplicative modulaire en Python

Question

Un module Python standard contient-il une fonction permettant de calculer inverse multiplicatif modulaire d'un nombre, c'est-à-dire un nombre y = invmod(x, p) tal que x*y == 1 (mod p) ? Google ne semble pas donner de bonnes indications à ce sujet.

Bien entendu, il est possible d'élaborer un 10-liner maison de algorithme euclidien étendu Mais pourquoi réinventer la roue ?

Par exemple, la fonction BigInteger a modInverse méthode. Python n'a-t-il pas quelque chose de similaire ?

Answer 1

Python 3.8+

y = pow(x, -1, p)

Python 3.7 et antérieur

Peut-être que quelqu'un trouvera cela utile (de wikibooks ):

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

Answer 2

Si votre module est premier (vous l'appelez p ), il suffit alors de calculer :

y = x**(p-2) mod p  # Pseudocode

Ou en Python proprement dit :

y = pow(x, p-2, p)

Voici quelqu'un qui a mis en œuvre des fonctionnalités de théorie des nombres en Python : http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html

Voici un exemple réalisé à l'invite :

m = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L

Answer 3

Vous pouvez également consulter le site gmpy module. Il s'agit d'une interface entre Python et la bibliothèque de précision multiple GMP. gmpy fournit une fonction d'inversion qui fait exactement ce dont vous avez besoin :

>>> import gmpy
>>> gmpy.invert(1234567, 1000000007)
mpz(989145189)

Réponse actualisée

Comme l'a noté @hyh , le gmpy.invert() renvoie 0 si l'inverse n'existe pas. Cela correspond au comportement de la fonction mpz_invert() fonction. gmpy.divm(a, b, m) fournit une solution générale au problème de la a=bx (mod m) .

>>> gmpy.divm(1, 1234567, 1000000007)
mpz(989145189)
>>> gmpy.divm(1, 0, 5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 8)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: not invertible
>>> gmpy.divm(1, 4, 9)
mpz(7)

divm() renverra une solution lorsque gcd(b,m) == 1 et soulève une exception si l'inverse multiplicatif n'existe pas.

Avertissement : je suis le mainteneur actuel de la bibliothèque gmpy.

Mise à jour de la réponse 2

gmpy2 lève maintenant correctement une exception lorsque l'inverse n'existe pas :

>>> import gmpy2

>>> gmpy2.invert(0,5)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: invert() no inverse exists

Answer 4

Depuis la version 3.8, la fonction pow() de python peut prendre un module et un entier négatif. Voir aquí . Leur argumentaire sur la façon de l'utiliser est le suivant

>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True

Answer 5

Voici un one-liner pour Lutte contre les codes ; c'est l'une des solutions les plus courtes :

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]

Il renverra -1 si A n'a pas d'inverse multiplicatif dans n .

Utilisation :

MMI(23, 99) # returns 56
MMI(18, 24) # return -1

La solution utilise le Algorithme euclidien étendu .