Modulares Inverses: das Element, das mod m „teilt"

Das modulare Inverse von a bezüglich des Moduls m ist die ganze Zahl x, so dass a · x ≡ 1 (mod m). Es existiert genau dann, wenn gcd(a, m) = 1, also a und m teilerfremd sind. Wenn es existiert, ist es eindeutig in {0, 1, ..., m−1} und wird mit a⁻¹ mod m bezeichnet. Beispiele: 3⁻¹ mod 7 = 5 (da 3·5 = 15 = 2·7 + 1); 10⁻¹ mod 17 = 12. 2⁻¹ mod 4 existiert nicht, da gcd(2,4) = 2. Grundlage der Arithmetik in ℤ/mℤ, verwendet in der Kryptographie (RSA, ElGamal, Diffie-Hellman), Codierungstheorie und numerischen Algorithmen.

Erweiterter Euklidischer Algorithmus

Die effizienteste Methode zur Berechnung von a⁻¹ mod m ist der erweiterte Euklidische Algorithmus, der Bezout-Koeffizienten x, y findet, so dass a·x + m·y = gcd(a, m). Wenn gcd(a,m)=1, dann a·x ≡ 1 (mod m), also ist x mod m das gesuchte Inverse. Komplexität O(log min(a,m)), viel schneller als Brute-Force O(m). Beispiel a=3, m=7: 7 = 2·3 + 1 → 1 = 7 − 2·3 → x = −2 ≡ 5 (mod 7). Also 3⁻¹ ≡ 5 (mod 7).

Modulare Exponentiation a^b mod m

Die Berechnung von a^b bei großem b ist mit direkten Multiplikationen unpraktikabel. Die binäre Exponentiation (square-and-multiply) reduziert die Kosten auf O(log₂ b) modulare Multiplikationen: schreibe b binär, iteriere bitweise, quadriere a in jedem Schritt, multipliziere mit a wenn das Bit 1 ist, reduziere jedes Mal mod m. Beispiel 7²¹ mod 100: 21 = 10101₂, Ergebnis 07. Fundamental in RSA (a^d mod n zur Entschlüsselung) und Primzahltests (Miller-Rabin, Fermat).

Kleiner Satz von Fermat und Satz von Euler

Wenn p prim und gcd(a,p)=1, dann a^(p−1) ≡ 1 (mod p) (Fermat). Daher a⁻¹ ≡ a^(p−2) mod p. Euler verallgemeinert: für beliebiges m gilt a^φ(m) ≡ 1 (mod m) wenn gcd(a,m)=1, wobei φ die Eulersche Phi-Funktion ist (Anzahl der zu m teilerfremden Zahlen in [1,m]). Für m = p·q (Produkt zweier verschiedener Primzahlen, RSA) ist φ(m) = (p−1)(q−1). Der chinesische Restsatz erlaubt die Zerlegung von mod-m-Berechnungen in mod-p- und mod-q-Berechnungen, die schneller sind.

Lineare Kongruenzen a·x ≡ b (mod m)

Eine Kongruenz a·x ≡ b (mod m) hat Lösungen genau dann, wenn d = gcd(a, m) ein Teiler von b ist. Dann gibt es genau d verschiedene Lösungen modulo m. Verfahren: dividiere die Kongruenz durch d, um a'·x ≡ b' (mod m') zu erhalten, wobei a'=a/d, b'=b/d, m'=m/d; die eindeutige Lösung ist x₀ = a'⁻¹ · b' (mod m'). Die d ursprünglichen Lösungen sind x₀, x₀+m', x₀+2m', ..., x₀+(d−1)m' (mod m).

Kryptographische Anwendungen

RSA: privater Schlüssel d = e⁻¹ mod φ(n), mit n=pq und e typischerweise 65537. Entschlüsselung: m = c^d mod n. Digitale Signatur: s = H(m)^d mod n. ElGamal und DSA verwenden Inverse mod q (Gruppenordnung). Elliptische Kurven (ECDSA, Ed25519): Skalarmultiplikation nutzt modulare Exponentiation über endlichen Körpern GF(p) und GF(2ⁿ). Hochgeschwindigkeits-kryptographisches Hashing erfordert modulare Multiplikationen auf 32-64-Bit-Wörtern.

Weitere Anwendungen

Hash-Algorithmen auf Primmoduli (Rabin-Karp-Stringsuche); Fehlerprüfung (CRC mit Polynomen in GF(2)); Reed-Solomon-Codes (Operationen in GF(2^m)); Pseudozufallsgeneratoren (LCG: Xₙ₊₁ = a·Xₙ + c mod m); Graphentheorie (Zyklen in Z/nZ); Kryptowährungen (secp256k1 in Bitcoin/Ethereum, Pairings in BLS12-381); Blockchain (zk-SNARK auf paarungsfreundlichen Kurven); Signaldezimierung (Resampling in DSP).

Anwendung

Modus wählen: Inverses (a, m → a⁻¹ mod m), Exponentiation (a, b, m → a^b mod m), Erweiterter Euklid (a, b → gcd, x, y sodass ax+by=gcd), Lineare Kongruenz (a, b, m → alle Lösungen von ax≡b mod m). Positive ganze Zahlen; m ≥ 2.

Die modulare Arithmetik, von der Uhr zu RSA

Die modulare Arithmetik, von Carl Friedrich Gauß in den Disquisitiones Arithmeticae von 1801 formalisiert, ist die Arithmetik der Reste: Wie die Stunden auf einem Zifferblatt "kehren" die Zahlen nach Erreichen des Moduls zurück. Das modulare Inverse ist die Operation, die diese Welt zu einem Körper macht, wenn der Modul prim ist, und so das "Dividieren" erlaubt. Auf dieser Struktur beruhen die RSA-Kryptographie, das Diffie-Hellman-Schlüsselaustauschprotokoll und die digitalen Signaturen, die jede Banktransaktion und jede sichere HTTPS-Verbindung authentifizieren.

Aktualisiert im Juli 2026