Berechnen Sie die modulare multiplikative Inverse in Python

1. Modular multiplikativ invers mit dem naiven iterativen Ansatz
2. Modulare multiplikative Inverse mit der eingebauten Funktion pow()

Wenn wir zwei Zahlen a und m haben, dann ist die modulare multiplikative Inverse von a x unter modulo m wenn:

a * x % m = 1

In diesem Fall existiert die multiplikative Inverse nur dann, wenn a und m relativ prim sind, d.h. wenn der grösste gemeinsame Teiler von a und m 1 ist.

Der Wert von x kann von 1 bis m-1 reichen.

Modular multiplikativ invers mit dem naiven iterativen Ansatz

Angenommen, wir müssen die multiplikative Inverse von a unter modulo m finden. Wenn die modulo-multiplikative Inverse existiert, kann ihr Wert von 1 bis m-1 reichen. Daher iterieren wir durch diesen Bereich und prüfen die Bedingung für die modulo-multiplikative Inverse. Wenn eine Zahl innerhalb des Bereichs die Bedingung erfüllt, haben wir die Zahl als modulo-multiplikative Inverse.

def find_mod_inv(a, m):

    for x in range(1, m):
        if (a % m) * (x % m) % m == 1:
            return x
    raise Exception("The modular inverse does not exist.")


a = 13
m = 22

try:
    res = find_mod_inv(a, m)
    print("The required modular inverse is: " + str(res))

except:
    print("The modular inverse does not exist.")

Ausgabe:

The required modular inverse is: 17

Hier haben wir eine Funktion namens find_mod_inv, die a und m als Eingabe nimmt und die multiplikative Inverse von a unter Modulo m zurückgibt.

Wenn die Zahl a keine multiplikative Inverse von a unter modulo m hat, löst sie eine Exception aus.

Aus dem obigen Beispiel können wir sehen, dass die modulare multiplikative Inverse von 13 unter modulo 22 17 ist.

Modulare multiplikative Inverse mit der eingebauten Funktion pow()

Wir können auch die eingebaute Funktion pow() von Python verwenden, um die modulare multiplikative Inverse einer Zahl zu berechnen.

a = 38
m = 97
res = pow(a, m - 2, m)
print("The required modular inverse is: " + str(res))

Ausgabe:

The required modular inverse is: 23

Um die modulo-multiplikative Inverse mit der Methode pow() zu berechnen, ist der erste Parameter der Methode pow() die Zahl, deren Modulo-Inverse gefunden werden soll, der zweite Parameter ist die Modulo-Reihenfolge subtrahiert um 2 und der letzte Parameter ist die Modulo-Reihenfolge.

Für Python 3.8 und höher können wir jedoch das zweite Argument durch -1 ersetzen.

a = 38
m = 97
res = pow(a, -1, m)
print("The required modular inverse is: " + str(res))

Ausgabe:

The required modular inverse is: 23