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

Sympy , ein Python-Modul für symbolische Mathematik, hat eine eingebaute modulare Umkehrfunktion, falls Sie keine eigene implementieren wollen (oder wenn Sie bereits Sympy 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 der Docstring: Sympy mod_inverse docstring auf Github

Answer 2

Hier ist ein prägnanter Einzeiler, der dies tut, ohne externe Bibliotheken zu verwenden.

# 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 es sich hierbei eigentlich nur um egcd handelt, das so gestrafft wurde, dass es nur den einzigen Koeffizienten von Interesse zurückgibt.

Answer 3

Ich habe verschiedene Lösungen aus diesem Thread ausprobiert, und am Ende habe ich diese verwendet:

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

Modulare_Inverse in Python

Answer 4

Hier ist mein Code, es könnte schlampig sein, aber es scheint zu funktionieren für mich sowieso.

# 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

Answer 5

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

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