Modulare Arithmetik

Rechnen auf dem Zifferblatt: Nimmt man die Reste beim Teilen als eigenständige Objekte ernst, entsteht daraus eine Algebra mit eigenen Gesetzen — und auf ihr ruht bis heute fast jede sichere Verbindung im Netz.

Als Nächstes empfohlen → Asymmetrische Kryptographie · CS·KI

Der Beitrag

1801 erschienen die Disquisitiones Arithmeticae — das Werk, mit dem der erst vierundzwanzigjährige Carl Friedrich Gauß die moderne Zahlentheorie begründete und das ihm, zusammen mit seiner Vorhersage aus demselben Jahr, wo der verloren gegangene Zwergplanet Ceres wieder auftauchen würde, europäischen Ruhm eintrug. Unter den vielen Neuerungen des Buches findet sich ein täuschend schlichter Kniff der Notation: Man schreibe a ≡ b (mod n), wenn a und b beim Teilen durch n denselben Rest lassen. Aus dem Rechnen auf dem Zifferblatt — nach der 12 kommt wieder die 1 — machte diese Schreibweise eine ernstzunehmende algebraische Struktur mit eigenen Gesetzen. Und auf dem Gerüst, das Gauß um sie herum errichtete, ruht bis heute fast jede sichere Verbindung im Internet.

Kongruent modulo n heißen zwei ganze Zahlen a und b — geschrieben a ≡ b (mod n) —, wenn n ihre Differenz teilt, also a − b = kn für eine ganze Zahl k gilt; gleichwertig: wenn beide beim Teilen durch n denselben Rest lassen. Kongruenz ist eine Äquivalenzrelation — reflexiv, symmetrisch, transitiv —, und ihre Äquivalenzklassen, die Restklassen mod n, sind genau n an der Zahl: {0, 1, 2, …, n−1}. Die modulare Arithmetik ist die Algebra dieser Klassen. Addition, Subtraktion und Multiplikation vertragen sich mit der Kongruenz: Aus a ≡ a' und b ≡ b' (mod n) folgt a + b ≡ a' + b' (mod n) und ab ≡ a'b' (mod n). Heikler ist die Division: Ein multiplikatives Inverses mod n besitzt a genau dann, wenn gcd(a, n) = 1. Ist n eine Primzahl, so hat jede Restklasse außer der Null ein Inverses — ℤ/n wird zum endlichen Körper, einer Struktur mit allen algebraischen Eigenschaften der rationalen Zahlen. Der kleine Satz von Fermat besagt: Für jede Primzahl p und jedes nicht durch p teilbare a gilt aᵖ⁻¹ ≡ 1 (mod p). Der Satz von Euler hebt das ins Allgemeine: a^φ(n) ≡ 1 (mod n) für gcd(a, n) = 1, wobei die Eulersche Phi-Funktion φ(n) zählt, wie viele der Zahlen von 1 bis n zu n teilerfremd sind. Der Chinesische Restsatz garantiert: Ein System von Kongruenzen zu paarweise teilerfremden Moduln hat modulo dem Produkt genau eine Lösung. Und das quadratische Reziprozitätsgesetz — Gauß nannte es das theorema aureum, den goldenen Satz, und bewies es auf acht verschiedene Weisen — verschränkt die Lösbarkeit von x² ≡ p (mod q) mit der von x² ≡ q (mod p); die Legendre- und Jacobi-Symbole bauen den Apparat weiter aus.

Warum jetztAuf der modularen Arithmetik ruht die gesamte Public-Key-Kryptographie. RSA funktioniert, weil sich große zusammengesetzte Zahlen n = pq nur mühsam faktorisieren lassen, modulare Potenzen aber leicht zu berechnen sind. Der Diffie-Hellman-Schlüsselaustausch nutzt diskrete Logarithmen in (ℤ/p)∗. Die Elliptische-Kurven-Kryptographie — das Zugpferd von TLS, Bitcoin und Signal — rechnet mit Punkten auf elliptischen Kurven über endlichen Körpern. Hashfunktionen verteilen in der Informatik Eingaben per Restbildung über Hashtabellen. Fehlerkorrigierende Codes — Reed-Solomon für QR-Codes und CDs, BCH für die Satellitenkommunikation — entstehen über endlichen Körpern. Und Pseudozufallsgeneratoren wie der Mersenne-Twister, der in Python, R und MATLAB bis heute eingebaut ist, beruhen auf modularen Operationen. Die kleine Äquivalenzrelation, die Gauß 1801 in eine Notation fasste, sichert heute jede HTTPS-Verbindung der Welt.