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

Python 3.8+

y = pow(x, -1, p)

Python 3.7 und früher

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

Wenn Ihr Modulus primär ist (Sie nennen es p ), dann können Sie einfach rechnen:

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

Oder in Python selbst:

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

Hier ist jemand, der einige Fähigkeiten der Zahlentheorie in Python implementiert hat: http://www.math.umbc.edu/~campbell/Computer/Python/numbthy.html

Hier ist ein Beispiel, das an der Eingabeaufforderung gemacht wurde:

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

Answer 3

Sie sollten sich auch die gmpy Modul. Es ist eine Schnittstelle zwischen Python und der GMP-Bibliothek für Mehrfachpräzision. gmpy bietet eine Invertierungsfunktion, die genau das tut, was Sie brauchen:

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

Aktualisierte Antwort

Wie von @hyh angemerkt, ist die gmpy.invert() gibt 0 zurück, wenn die Umkehrung nicht existiert. Das entspricht dem Verhalten von GMP's 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() wird eine Lösung zurückgeben, wenn gcd(b,m) == 1 und löst eine Ausnahme aus, wenn die multiplikative Umkehrung nicht existiert.

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

Aktualisierte Antwort 2

gmpy2 löst nun korrekt eine Ausnahme aus, wenn die Inverse nicht existiert:

>>> import gmpy2

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

Answer 4

Seit Version 3.8 kann Pythons Funktion pow() einen Modulus und eine negative ganze Zahl annehmen. Siehe aquí . Ihre Argumente für die Verwendung sind

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

Answer 5

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 -1 si A hat keine multiplikative Umkehrung in n .

Verwendung:

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

Die Lösung verwendet die Erweiterter Euklidischer Algorithmus .