Modularithmetik

Modularithmetik (häufig auch Modulararithmetik genannt) beschäftigt sich mit der Arithmetik der ganzen Zahlen modulo eines festen Modulus n. Zwei Zahlen a und b erfüllen a ≡ b (mod n), wenn n den Unterschied a − b teilt. Die Äquivalenzklassen modulo n heißen Residuen; Z/nZ bezeichnet man als die Menge der Residuen.

Grundoperationen wie Addition, Subtraktion, Multiplikation und Potenzierung werden modulo n durchgeführt; das Ergebnis wird nach jeder Operation auf den Rest modulo n reduziert. Beispiel: 7 + 10 ≡ 5 (mod 12). Die Restklassen repräsentieren 0 bis n−1.

Die Residuen bilden zusammen mit den Operationen eine algebraische Struktur; Z/nZ ist ein Ring. Für manche Moduli, insbesondere wenn n prim ist, ist es sogar ein Körper, in dem Division interpretierbar ist.

Invertierbarkeit: Ein multiplikatives Inverses von a modulo n existiert genau dann, wenn gcd(a,n)=1. Das Inverse x erfüllt a·x ≡ 1 (mod n). Der erweiterte Euklidische Algorithmus liefert x.

Wichtige Sätze: Fermats kleiner Satz (für Primzahlen p, gcd(a,p)=1: a^(p−1) ≡ 1 (mod p)). Euler's Theorem: gcd(a,n)=1 ⇒ a^φ(n) ≡ 1 (mod n). Chinesischer Restsatz: Sind m1,...,mk paarweise zueinander teilerfremd, existiert eine eindeutige Lösung modulo M=∏mi für ein System von Kongruenzen a ≡ bi (mod mi).

Berechnung: Modulare Exponentiation erfolgt effizient durch Exponentiation durch Quadratur; Zwischenstände werden regelmäßig reduziert, sodass große Exponenten praktikabel bleiben.

Anwendungen: Modulararithmetik bildet das Fundament moderner Kryptografie wie RSA, Diffie-Hellman und elliptische Kurven. Sie findet Verwendung in Signaturen, Prüfsummen, Zufallszahlengeneratoren und numerischen Algorithmen; in der Zahlentheorie dient sie zum Beweis wichtiger Sätze.

Historischer Kontext: Die Grundideen reichen bis in die Antike; systematisiert wurden sie von Gauss und in der Entwicklung der Zahlentheorie im 19. Jahrhundert.