Modulare multiplikative Umkehrfunktion in Python

Question

Enthält ein Standard-Python-Modul eine Funktion zur Berechnung von modulare multiplikative Umkehrung einer Zahl, d.h. einer Zahl y = invmod(x, p) tal que x*y == 1 (mod p) ? Google scheint hier keine guten Hinweise zu geben.

Natürlich kann man mit selbstgebrauten 10-Linern von erweiterter euklidischer Algorithmus aber warum das Rad neu erfinden.

Zum Beispiel, Java's BigInteger hat modInverse Methode. Gibt es in Python nicht etwas Ähnliches?

Answer 1

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

Laut dem Kommentar über diesem Code können kleine negative Werte zurückgegeben werden, so dass Sie möglicherweise prüfen könnten, ob negativ und addieren n, wenn negativ vor der Rückgabe b.

Answer 2

Um die modulare multiplikative Umkehrung zu berechnen, 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

Answer 3

Nun, ich habe keine Funktion in Python, aber ich habe eine Funktion in C, die Sie leicht in Python konvertieren können, in der untenstehenden C-Funktion wird der erweiterte euklidische Algorithmus zur Berechnung des inversen Mods verwendet.

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 oben genannte C-Funktion ist dem folgenden Link entnommen C-Programm zur Ermittlung der modularen multiplikativen Inverse von zwei relativen Primzahlen