Modulares Inverses berechnen

Das modulare Inverse einer ganzen Zahl a modulo m ist eine Zahl x, für die a × x bei Division durch m den Rest 1 lässt. Es wird als a⁻¹ mod m geschrieben und liegt bei vorhandener Lösung im Bereich von 0 bis m − 1. Zum Beispiel ist 4 das Inverse von 3 modulo 11, weil 3 × 4 = 12 und 12 bei Division durch 11 den Rest 1 lässt.

Ein modulares Inverses existiert genau dann, wenn der größte gemeinsame Teiler von a und m gleich 1 ist. Sind die Zahlen nicht teilerfremd, kann kein ganzzahliges Vielfaches von a modulo m den Rest 1 ergeben. Für 6 modulo 9 gilt beispielsweise ggT(6, 9) = 3, daher gibt es dort kein modulares Inverses.

Der erweiterte euklidische Algorithmus bestimmt ganze Zahlen s und t mit s × a + t × m = ggT(a, m). Bei einem ggT von 1 ergibt sich s × a + t × m = 1. Nach der Reduktion modulo m ist s daher das gesuchte Inverse. Der Rechner zeigt jede Rest-, Koeffizienten- und Prüfrechnung in einer Tabelle.

Bei RSA wird ein privater Exponent als Inverses eines öffentlichen Exponenten modulo einer Zahl aus den Primfaktoren gebildet. Dadurch kann die Verschlüsselung mathematisch rückgängig gemacht werden. Der Rechner veranschaulicht den zugrunde liegenden Algorithmus mit kleinen ganzzahligen Eingaben, ersetzt aber keine sichere Kryptografiebibliothek.

Gesucht ist x mit 3 × x ≡ 1 (mod 11). Der Algorithmus startet mit den Resten 11 und 3 und gelangt über 2 zum ggT 1. Die zugehörigen Koeffizienten liefern 4 × 3 + (−1) × 11 = 1. Damit ist das Inverse 4 und die Prüfung 3 × 4 mod 11 = 1.