Modulare multiplikative Inversfunktion in Python

Enthält ein Standard-Python-Modul eine Funktion zum Berechnen der modularen multiplikativen Inversen einer Zahl, dh einer y = invmod(x, p)solchen Zahl x*y == 1 (mod p)? Google scheint hierzu keine guten Hinweise zu geben.

Natürlich kann man sich einen selbst gebrauten 10-Liner mit erweitertem euklidischen Algorithmus einfallen lassen , aber warum das Rad neu erfinden?

Zum Beispiel hat Java BigIntegereine modInverseMethode. Hat Python nicht etwas Ähnliches?

Vielleicht findet jemand dies nützlich (aus 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

Wenn Ihr Modul prim ist (Sie nennen es p), können Sie einfach berechnen:

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

Oder in Python:

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

Hier ist jemand, der einige Funktionen der Zahlentheorie in Python implementiert hat: http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html

Hier ist ein Beispiel an der Eingabeaufforderung:

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

Vielleicht möchten Sie sich auch das gmpy- Modul ansehen . Es ist eine Schnittstelle zwischen Python und der GMP-Bibliothek mit mehrfacher Genauigkeit. gmpy bietet eine Invertierungsfunktion, die genau das tut, was Sie brauchen:

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

Antwort aktualisiert

Wie von @hyh angegeben, gmpy.invert()gibt die 0 zurück, wenn die Umkehrung nicht existiert. Das entspricht dem Verhalten der GMP- mpz_invert()Funktion. gmpy.divm(a, b, m)bietet eine allgemeine Lösung für 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()gibt eine Lösung zurück, wenn gcd(b,m) == 1und löst eine Ausnahme aus, wenn die multiplikative Inverse nicht existiert.

Haftungsausschluss: Ich bin der aktuelle Betreuer der gmpy-Bibliothek.

Aktualisierte Antwort 2

gmpy2 löst jetzt ordnungsgemäß eine Ausnahme aus, wenn die Umkehrung nicht vorhanden ist:

>>> import gmpy2

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

Ab 3.8 Python kann die pow () -Funktion einen Modul und eine negative ganze Zahl annehmen. Siehe hier . Ihr Fall für die Verwendung ist

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

Hier ist ein Einzeiler für CodeFights ; Es ist eine der kürzesten Lösungen:

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]

Es wird zurückgegeben, -1wenn Akeine multiplikative Inverse in vorhanden ist n.

Verwendung:

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

Die Lösung verwendet den erweiterten euklidischen Algorithmus .

Sympy , ein Python-Modul für symbolische Mathematik, verfügt über eine integrierte modulare Umkehrfunktion, wenn Sie keine eigene implementieren möchten (oder wenn Sie Sympy bereits verwenden):

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'

Dies scheint nicht auf der Sympy-Website dokumentiert zu sein, aber hier ist die Dokumentzeichenfolge: Sympy mod_inverse docstring auf Github

Hier ist mein Code, er mag schlampig sein, aber er scheint trotzdem für mich zu funktionieren.

# 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

Der obige Code läuft nicht in Python3 und ist im Vergleich zu den GCD-Varianten weniger effizient. Dieser Code ist jedoch sehr transparent. Es hat mich veranlasst, eine kompaktere Version zu erstellen:

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

Hier ist ein prägnanter 1-Liner, der dies ohne Verwendung externer Bibliotheken tut.

# 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

Beachten Sie, dass dies wirklich nur egcd ist und optimiert wurde, um nur den einzelnen interessierenden Koeffizienten zurückzugeben.

Um die modulare multiplikative Inverse herauszufinden, empfehle ich die Verwendung des erweiterten euklidischen Algorithmus wie folgt:

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

Ich probiere verschiedene Lösungen aus diesem Thread aus und am Ende benutze ich diese:

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 in Python

Nun, ich habe keine Funktion in Python, aber ich habe eine Funktion in C, die Sie leicht in Python konvertieren können. In der folgenden c-Funktion wird der erweiterte Euklidian-Algorithmus verwendet, um den inversen Mod zu berechnen.

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;}

Python-Funktion

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

Der Verweis auf die obige C-Funktion wird aus dem folgenden Link- C-Programm entnommen , um die modulare multiplikative Inverse zweier relativ Primzahlen zu finden

von der CPython Implementierung Quellcode :

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

Gemäß dem Kommentar über diesem Code kann er kleine negative Werte zurückgeben, sodass Sie möglicherweise prüfen können, ob er negativ ist, und n hinzufügen können, wenn er negativ ist, bevor Sie b zurückgeben.

Viele der oben genannten Links sind zum 23.01.2017 defekt. Ich habe diese Implementierung gefunden: https://courses.csail.mit.edu/6.857/2016/files/ffield.py