Modulare Arithmetik erklärt
Jeder rechnet bereits modular: 10 Stunden nach 8 Uhr ist es 6 Uhr, und der Tag nach Sonntag ist Montag. Ein Zählen, das nach n Schritten wieder bei 0 beginnt, hat, wie sich zeigt, eine eigene vollständige Arithmetik, mit Regeln, Überraschungen und einem zentralen Platz in der Zahlentheorie und in der Kryptographie, die das Internet schützt.
Reste und Kongruenz
Teilen Sie a durch n und behalten Sie nur den Rest: Das ist a mod n, eine Zahl von 0 bis n − 1. 26 mod 7 = 5, denn 26 = 3 × 7 + 5. Zahlen mit demselben Rest verhalten sich mod n gleich, deshalb nennt man sie kongruent: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauß führte diese Schreibweise 1801 in seinen Disquisitiones Arithmeticae ein, und sie machte aus den alten Beobachtungen von Fermat und Euler eine eigene Arithmetik. Auf einer Uhr mit n Positionen landet jede ganze Zahl auf ihrem Rest; die vollen Umdrehungen werden vergessen.
Addieren, Subtrahieren und Multiplizieren
Die drei gewöhnlichen Rechenarten funktionieren wie gewohnt, und Sie dürfen jederzeit mod n reduzieren: Der Rest einer Summe ist der Rest der Summe der Reste, und dasselbe gilt für Differenzen und Produkte. Um die letzte Ziffer von 37 × 48 zu finden, multiplizieren Sie nur die letzten Ziffern: 7 × 8 = 56, das Ergebnis endet also auf 6. Genau das macht modulare Arithmetik für Computer so nützlich: Egal wie groß die Zahlen sind, die Zwischenwerte übersteigen nie n².
Division braucht ein Inverses
Die Division ist die Ausnahme. 2 × 3 ≡ 2 × 8 (mod 10), denn beide sind 6 mod 10, doch 3 und 8 sind verschieden, man kann die 2 also nicht einfach kürzen. Durch a zu dividieren heißt, mit seinem Inversen zu multiplizieren, der Zahl x mit a × x ≡ 1, und das existiert genau dann, wenn a und n keinen gemeinsamen Teiler haben. Der erweiterte euklidische Algorithmus findet es: Er durchläuft die Divisionsschritte von Euklid für den größten gemeinsamen Teiler und notiert bei jedem Schritt einen Multiplikator, sodass der Multiplikator das Inverse ist, sobald der Rest 1 erreicht. Ist n eine Primzahl, hat jede Zahl außer 0 ein Inverses, und die Division funktioniert immer.
Potenzen, Fermat und Euler
Potenzen wiederholen sich. Nehmen Sie die Potenzen von 3 mod 7: 3, 2, 6, 4, 5, 1 und dann wieder 3. Die Länge dieses Zyklus ist die Ordnung von 3. 1640 bemerkte Pierre de Fermat, dass für eine Primzahl p stets a^(p − 1) ≡ 1 (mod p) gilt, wenn p nicht a teilt, sodass jede Ordnung p − 1 teilt. Leonhard Euler bewies es und verallgemeinerte es auf jedes n, wobei p − 1 durch die Anzahl der zu n teilerfremden Werte ersetzt wird. Riesige Potenzen werden durch wiederholtes Quadrieren berechnet: a, a², a⁴, a⁸ …, jede das Quadrat der vorigen, reduziert mod n, und dann für die Binärziffern des Exponenten multipliziert.
Prüfziffern und Kalender
Modulare Arithmetik deckt Fehler auf. Die letzte Ziffer einer ISBN-10 wird so gewählt, dass eine gewichtete Summe aller zehn Ziffern ein Vielfaches von 11 ist, sodass jede einzelne falsche Ziffer und jede Vertauschung zweier Nachbarn erkannt wird. Bankkartennummern verwenden die Luhn-Prüfung mod 10 und IBANs eine Prüfung mod 97. Kalender laufen mod 7: Der Wochentag jedes Datums lässt sich mit wenigen Resten ermitteln, und so funktionieren ewige Kalender und die Doomsday-Regel.
Kryptographie
Die moderne Kryptographie beruht auf modularen Potenzen, die leicht zu berechnen und schwer umzukehren sind. Beim Diffie–Hellman-Schlüsselaustausch von 1976 einigen sich zwei Personen über eine offene Leitung auf ein gemeinsames Geheimnis, indem sie Potenzen modulo einer großen Primzahl austauschen. RSA, 1977 von Rivest, Shamir und Adleman veröffentlicht, verschlüsselt eine Nachricht m als m^e mod n, wobei n das Produkt zweier großer Primzahlen ist, und entschlüsselt mit einem zweiten Exponenten d, den nur berechnen kann, wer die beiden Primzahlen kennt. Im Lehrbuchbeispiel ist n = 3233 = 61 × 53, e = 17 und d = 413: Aus 65 wird 2790, und aus 2790 wird wieder 65.
Selbst ausprobieren
Öffnen Sie die Modulo-Uhr, um a mod n, Summen, Differenzen, Produkte, Potenzen, Inverse und Quotienten mod n für Zahlen mit bis zu 30 Stellen zu berechnen. Zu jedem Ergebnis gibt es die Schritte: die Division mit Rest, die Potenzen aus dem wiederholten Quadrieren oder die Tabelle des erweiterten euklidischen Algorithmus. Die Uhr zeichnet, wie das Ergebnis zustande kommt, von der Spirale einer Addition bis zum Zyklus der Potenzen, und für kleine n zeigt die Tabelle der Rechenart alle Ergebnisse auf einmal.
Häufig gestellte Fragen
Was bedeutet das Zeichen ≡?
a ≡ b (mod n) besagt, dass a und b bei Division durch n denselben Rest lassen, oder gleichbedeutend, dass n die Differenz a − b teilt. 38 ≡ 2 (mod 12), denn 38 − 2 = 36 ist ein Vielfaches von 12.
Ist mod dasselbe wie der Operator % beim Programmieren?
Für positive Zahlen ja. Für negative Zahlen liefern viele Sprachen wie C, Java und JavaScript einen negativen Rest: −7 % 3 ergibt dort −1, während −7 mod 3 = 2 ist. Der Operator % von Python folgt für positives n der mathematischen Konvention.
Was ist die Ordnung einer Zahl mod n?
Das kleinste k > 0 mit a^k ≡ 1 (mod n). Sie existiert nur, wenn a und n keinen gemeinsamen Teiler haben. Die Ordnung von 2 mod 7 ist 3, denn 2³ = 8 ≡ 1, und die Ordnung von 3 mod 7 ist 6, sodass die Potenzen von 3 jeden von null verschiedenen Rest durchlaufen: 3 ist eine Primitivwurzel mod 7.
Wer hat die modulare Arithmetik erfunden?
Reste wurden schon lange vorher verwendet, etwa im chinesischen Restsatz aus dem 3. bis 5. Jahrhundert und von Fermat und Euler. Gauß machte 1801 daraus eine systematische Arithmetik mit der Schreibweise der Kongruenzen.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Modulo-Uhr öffnen