Fonction inverse multiplicative modulaire en Python

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

Bien sûr, on peut proposer un algorithme euclidien étendu à 10 lignes , mais pourquoi réinventer la roue.

Par exemple, Java's BigIntegerhas modInversemethod. Python n'a-t-il pas quelque chose de similaire?

Peut-être que quelqu'un trouvera cela utile (à partir 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

Si votre module est premier (vous l'appelez p), vous pouvez simplement calculer:

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

Ou en Python proprement dit:

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

Voici quelqu'un qui a implémenté quelques capacité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

Vous pouvez également consulter le module gmpy . C'est une interface entre Python et la bibliothèque multi-précision 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 mise à jour

Comme indiqué par @hyh, le gmpy.invert()renvoie 0 si l'inverse n'existe pas. Cela correspond au comportement de la mpz_invert()fonction de GMP . gmpy.divm(a, b, m)fournit une solution générale à 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()retournera une solution quand gcd(b,m) == 1et lèvera une exception lorsque l'inverse multiplicatif n'existe pas.

Clause de non-responsabilité: je suis le mainteneur actuel de la bibliothèque gmpy.

Réponse mise à jour 2

gmpy2 lève désormais 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

À partir de 3.8 pythons, la fonction pow () peut prendre un module et un entier négatif. Regardez ici . Leur cas pour savoir comment l'utiliser est

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

Voici un one-liner pour CodeFights ; 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 retournera -1si An'a pas d'inverse multiplicatif dansn .

Usage:

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

La solution utilise l' algorithme euclidien étendu .

Sympy , un module python pour les mathématiques symboliques, a une fonction inverse modulaire intégrée si vous ne voulez pas implémenter la vôtre (ou si vous utilisez déjà Sympy):

from sympy import mod_inverse

mod_inverse(11, 35) # returns 16
mod_inverse(15, 35) # raises ValueError: 'inverse of 15 (mod 35) does not exist'

Cela ne semble pas être documenté sur le site Web de Sympy, mais voici la docstring: Sympy mod_inverse docstring sur Github

Voici mon code, il peut être bâclé mais il semble fonctionner pour moi de toute façon.

# a is the number you want the inverse for
# b is the modulus

def mod_inverse(a, b):
    r = -1
    B = b
    A = a
    eq_set = []
    full_set = []
    mod_set = []

    #euclid's algorithm
    while r!=1 and r!=0:
        r = b%a
        q = b//a
        eq_set = [r, b, a, q*-1]
        b = a
        a = r
        full_set.append(eq_set)

    for i in range(0, 4):
        mod_set.append(full_set[-1][i])

    mod_set.insert(2, 1)
    counter = 0

    #extended euclid's algorithm
    for i in range(1, len(full_set)):
        if counter%2 == 0:
            mod_set[2] = full_set[-1*(i+1)][3]*mod_set[4]+mod_set[2]
            mod_set[3] = full_set[-1*(i+1)][1]

        elif counter%2 != 0:
            mod_set[4] = full_set[-1*(i+1)][3]*mod_set[2]+mod_set[4]
            mod_set[1] = full_set[-1*(i+1)][1]

        counter += 1

    if mod_set[3] == B:
        return mod_set[2]%B
    return mod_set[4]%B

Le code ci-dessus ne fonctionnera pas en python3 et est moins efficace que les variantes de GCD. Cependant, ce code est très transparent. Cela m'a incité à créer une version plus compacte:

def imod(a, n):
 c = 1
 while (c % a > 0):
     c += n
 return c // a

Voici un 1-liner concis qui le fait, sans utiliser de bibliothèques externes.

# Given 0<a<b, returns the unique c such that 0<c<b and a*c == gcd(a,b) (mod b).
# In particular, if a,b are relatively prime, returns the inverse of a modulo b.
def invmod(a,b): return 0 if a==0 else 1 if b%a==0 else b - invmod(b%a,a)*b//a

Notez qu'il ne s'agit en réalité que de egcd, simplifié pour ne renvoyer que le seul coefficient d'intérêt.

Pour comprendre l'inverse multiplicatif modulaire, je recommande d'utiliser l'algorithme euclidien étendu comme ceci:

def multiplicative_inverse(a, b):
    origA = a
    X = 0
    prevX = 1
    Y = 1
    prevY = 0
    while b != 0:
        temp = b
        quotient = a/b
        b = a%b
        a = temp
        temp = X
        a = prevX - quotient * X
        prevX = temp
        temp = Y
        Y = prevY - quotient * Y
        prevY = temp

    return origA + prevY

J'essaie différentes solutions de ce fil et à la fin j'utilise celle-ci:

def egcd(a, b):
    lastremainder, remainder = abs(a), abs(b)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient*x, x
        y, lasty = lasty - quotient*y, y
    return lastremainder, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)


def modinv(a, m):
    g, x, y = self.egcd(a, m)
    if g != 1:
        raise ValueError('modinv for {} does not exist'.format(a))
    return x % m

Modular_inverse en Python

Eh bien, je n'ai pas de fonction en python mais j'ai une fonction en C que vous pouvez facilement convertir en python, dans la fonction c ci-dessous, l'algorithme euclidien étendu est utilisé pour calculer le mod inverse.

int imod(int a,int n){
int c,i=1;
while(1){
    c = n * i + 1;
    if(c%a==0){
        c = c/a;
        break;
    }
    i++;
}
return c;}

Fonction Python

def imod(a,n):
  i=1
  while True:
    c = n * i + 1;
    if(c%a==0):
      c = c/a
      break;
    i = i+1

  return c

La référence à la fonction C ci-dessus est tirée du programme lien C suivant pour trouver l'inverse multiplicatif modulaire de deux nombres relativement premiers

à partir du code source de l' implémentation cpython :

def invmod(a, n):
    b, c = 1, 0
    while n:
        q, r = divmod(a, n)
        a, b, c, n = n, c, b - q*c, r
    # at this point a is the gcd of the original inputs
    if a == 1:
        return b
    raise ValueError("Not invertible")

selon le commentaire ci-dessus ce code, il peut renvoyer de petites valeurs négatives, vous pouvez donc potentiellement vérifier si négatif et ajouter n lorsqu'il est négatif avant de renvoyer b.

La plupart des liens ci-dessus sont rompus au 23/01/2017. J'ai trouvé cette implémentation: https://courses.csail.mit.edu/6.857/2016/files/ffield.py