Effiziente Berechnung der multiplikativen Inversen modulo n in Python

Das modulare multiplikative Inverse ist ein grundlegendes Konzept in der Zahlentheorie und Kryptographie. Es ist eine Zahl, die, wenn sie mit einer anderen Zahl multipliziert und modulo eines gegebenen Moduls genommen wird, ein Ergebnis von 1 liefert. Dieser Artikel untersucht verschiedene effiziente Algorithmen zur Berechnung des modularen multiplikativen Inversen in Python und vergleicht deren Effizienz und Anwendbarkeit.

Inhaltsverzeichnis

1. Naiver iterativer Ansatz
2. Modulare Exponentiation (Fermats kleiner Satz)
3. Erweiterter Euklidischer Algorithmus
4. Fazit

1. Naiver iterativer Ansatz

Dieser einfache Ansatz iteriert durch mögliche Inverse, bis er eines findet, das die Bedingung erfüllt. Obwohl er einfach zu verstehen ist, ist seine Zeitkomplexität von O(m) für große Moduli sehr ineffizient.

def modular_inverse_naive(a, m):
    """
    Berechnet das modulare multiplikative Inverse mit einem naiven iterativen Ansatz.

    Args:
        a: Die Zahl, für die das Inverse gefunden werden soll.
        m: Der Modul.

    Returns:
        Das modulare multiplikative Inverse von a modulo m oder None, wenn es nicht existiert.
    """
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# Beispiel Verwendung
a = 3
m = 11
inverse = modular_inverse_naive(a, m)
print(f"Das modulare multiplikative Inverse von {a} modulo {m} ist: {inverse}")  # Ausgabe: 4

2. Modulare Exponentiation (Fermats kleiner Satz)

Wenn der Modul m prim ist, bietet Fermats kleiner Satz eine effiziente Lösung. Er besagt, dass a^p-1 ≡ 1 (mod p) für jede ganze Zahl a gilt, die nicht durch p teilbar ist. Daher ist das Inverse a^p-2 (mod p), effizient berechenbar mittels modularer Exponentiation. Diese Methode hat eine Zeitkomplexität von O(log m).

def modular_exponentiation(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return res

def modular_inverse_fermat(a, p):
  if p <= 1:
    raise ValueError("p muss eine Primzahl größer als 1 sein")
  return modular_exponentiation(a, p - 2, p)

# Beispiel Verwendung (p ist prim)
a = 3
p = 11
inverse = modular_inverse_fermat(a, p)
print(f"Das modulare multiplikative Inverse von {a} modulo {p} ist: {inverse}")  # Ausgabe: 4

3. Erweiterter Euklidischer Algorithmus

Der erweiterte Euklidische Algorithmus ist die allgemeinste und effizienteste Methode, anwendbar auf jeden Modul. Er findet den größten gemeinsamen Teiler (GGT) zweier Zahlen und drückt ihn als Linearkombination dieser Zahlen aus. Wenn der GGT 1 ist, existiert das modulare Inverse und ist leicht zu erhalten. Dieser Algorithmus hat ebenfalls eine Zeitkomplexität von O(log m).

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modular_inverse_euclidean(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # Inverses existiert nicht
    else:
        return x % m

# Beispiel Verwendung
a = 3
m = 11
inverse = modular_inverse_euclidean(a, m)
print(f"Das modulare multiplikative Inverse von {a} modulo {m} ist: {inverse}")  # Ausgabe: 4

a = 5
m = 12
inverse = modular_inverse_euclidean(a, m)
print(f"Das modulare multiplikative Inverse von {a} modulo {m} ist: {inverse}")  # Ausgabe: None

4. Fazit

Dieser Artikel präsentierte drei Algorithmen zur Berechnung des modularen multiplikativen Inversen. Der naive Ansatz ist einfach, aber ineffizient. Fermats kleiner Satz bietet eine effiziente Lösung für Primzahlmodule. Der erweiterte Euklidische Algorithmus ist die vielseitigste und effizienteste Methode, anwendbar auf jeden Modul, in dem das Inverse existiert, was ihn zur bevorzugten Wahl für die meisten Anwendungen, insbesondere in der Kryptographie, macht.