Modulo-Rechner mit modularer Inverse

Modulare Arithmetik mit BigInt

Der Modulo-Rechner rechnet mit Restklassen: a mod m ist der Rest bei der Division von a durch m, immer als Zahl zwischen 0 und m − 1. Dazu kommen die wichtigsten Operationen der Zahlentheorie: modulares Potenzieren (a^b mod m) mit dem Verfahren „Square and Multiply“, die modulare Inverse und der erweiterte euklidische Algorithmus, der neben dem ggT auch die Bézout-Koeffizienten s und t mit s·a + t·m = ggT(a, m) liefert.

Alle Rechnungen laufen mit BigInt, also ohne Rundung und mit beliebig vielen Stellen. Damit lassen sich auch Werte aus der Kryptografie nachrechnen. Das Beispiel RSA lädt die Lehrbuchwerte p = 61, q = 53: Mit n = 3233, φ(n) = 3120 und e = 17 ergibt die modulare Inverse den privaten Exponenten d = 2753. Die Tabelle zeigt jeden Schritt des erweiterten euklidischen Algorithmus mit Rest r, Quotient q und den Koeffizienten s und t.

Grenzen: Negative Exponenten werden als Potenz der Inversen gerechnet, das geht nur, wenn die Inverse existiert. Sehr große Exponenten sind schnell, sehr große Moduln mit Tausenden Stellen können aber einige Sekunden dauern. Für Primzahltests nutzen Sie den Rechner Primzahl prüfen.