Die Bibliothek · MathematikTafel № 179 · Folio I
ILL. № 179
MATH
Plate — Modulare Arithmetik
·Tafel № 179

Modulare Arithmetik

Uhrenarithmetik — was beim Teilen übrig bleibt, als eigenständiges System genommen.
Als Nächstes empfohlen → Asymmetrische Kryptographie · CS·KI
Facetten
  • Congruence mod n and residue classesnoch nicht geprüft
  • Addition, multiplication, and inverses mod nnoch nicht geprüft
  • Fermat, Euler, and the Chinese Remainder Theoremnoch nicht geprüft
  • The bedrock of public-key cryptographynoch nicht geprüft
Der Beitrag

Im Jahr 1801 legte ein vierundzwanzigjähriger Carl Friedrich Gauß die Disquisitiones Arithmeticae vor — das Buch, das die moderne Zahlentheorie begründete und, zusammen mit seiner Vorhersage im selben Jahr, wo der verloren geglaubte Zwergplanet Ceres wieder auftauchen würde, seinen Ruf in Europa begründete. Unter seinen vielen Neuerungen stand ein scheinbar harmloser Kniff in der Notation: schreibe a ≡ b (mod n), um auszudrücken, dass a und b beim Teilen durch n denselben Rest hinterlassen. Aus der Uhrenarithmetik — wie die Stunden von 12 wieder auf 1 umspringen — wurde damit eine ernsthafte algebraische Struktur mit eigenen Gesetzen. Der Rahmen, den Gauß um diese Notation legte, trägt heute jede sichere Verbindung des Internets.

Zwei ganze Zahlen a und b heißen kongruent modulo n, geschrieben a ≡ b (mod n), wenn n ihre Differenz teilt: a − b = kn für eine ganze Zahl k. Gleichbedeutend: a und b hinterlassen denselben Rest beim Teilen durch n. Die Kongruenz ist eine Äquivalenzrelation: reflexiv, symmetrisch, transitiv. Die Äquivalenzklassen sind die Restklassen mod n, und davon gibt es genau n: {0, 1, 2, …, n−1}. Die Modulararithmetik ist die Algebra dieser Klassen. Addition, Subtraktion und Multiplikation respektieren die Kongruenz: ist a ≡ a' und b ≡ b' (mod n), so ist a + b ≡ a' + b' (mod n) und ab ≡ a'b' (mod n). Die Division ist heikler: a besitzt ein multiplikatives Inverses mod n genau dann, wenn gcd(a, n) = 1. Ist n eine Primzahl, hat jeder von null verschiedene Rest ein Inverses, und ℤ/n ist ein endlicher Körper — eine Struktur mit allen algebraischen Eigenschaften der rationalen Zahlen. Der kleine Satz von Fermat: für jede Primzahl p und jede ganze Zahl a, die nicht durch p teilbar ist, gilt aᵖ⁻¹ ≡ 1 (mod p). Der Satz von Euler verallgemeinert das: a^φ(n) ≡ 1 (mod n), sofern gcd(a, n) = 1; dabei ist φ(n) die eulersche Totientenfunktion (die Anzahl der ganzen Zahlen von 1 bis n, die zu n teilerfremd sind). Der Chinesische Restsatz: ein System von Kongruenzen mit paarweise teilerfremden Modulen besitzt eine eindeutige Lösung modulo dem Produkt. Das quadratische Reziprozitätsgesetz — Gauß nannte es das theorema aureum, den goldenen Satz, und bewies es auf acht Weisen — verknüpft die Lösbarkeit von x² ≡ p (mod q) mit der von x² ≡ q (mod p). Die Legendre- und Jacobi-Symbole erweitern den Apparat.

Warum jetztDie Modulararithmetik trägt die gesamte Public-Key-Kryptographie. RSA lebt von der Schwierigkeit, große zusammengesetzte Zahlen n = pq zu faktorisieren, und von der leichten Berechnung modularer Potenzen. Der Diffie-Hellman-Schlüsselaustausch nutzt diskrete Logarithmen in (ℤ/p)\*. Die Elliptische-Kurven-Kryptographie — das Zugpferd des heutigen TLS, von Bitcoin und Signal — rechnet mit Punkten auf elliptischen Kurven über endlichen Körpern. Hashfunktionen in der Informatik verteilen Eingaben mittels Modulararithmetik über Hashtabellen. Fehlerkorrigierende Codes (Reed-Solomon für QR-Codes und CDs, BCH für Satellitenkommunikation) werden über endliche Körper konstruiert. Pseudozufallsgeneratoren — darunter der Mersenne-Twister, mit dem ein Großteil der Simulationsarbeit läuft — fußen auf modularen Operationen. Die kleine Äquivalenzrelation, die Gauß 1801 formalisierte, sichert jede HTTPS-Verbindung der modernen Welt.