Modulare Arithmetik ist Arithmetik auf einem Kreis. Zwei Zahlen sind modulo n kongruent, wenn sie sich um ein Vielfaches von n unterscheiden. Eine Uhr rechnet modulo 12: Zehn Stunden nach 5 Uhr ist 3 Uhr und nicht 15 Uhr. Diese einfache Idee liegt der modernen Kryptographie, Hashfunktionen, Fehlerkorrekturcodes und großen Teilen der Zahlentheorie zugrunde.
Jede Zeile und jede Spalte enthält {0,1,2,3,4} genau einmal. Die fünf Elemente bilden unter Addition modulo 5 eine abgeschlossene Gruppe. Rot markiert sind Summen, die über 4 hinausgehen und umklappen.
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
Modulare Arithmetik definiert Kongruenz: a ist kongruent zu b modulo n, wenn n die Differenz a-b teilt. Gauss systematisierte dieses Gebiet 1801. Sie bildet die Grundlage aller modernen Public-Key-Verfahren. RSA-Verschlüsselung beruht auf dem kleinen Satz von Fermat, der besagt, dass a^(p-1) kongruent zu 1 modulo p ist, sofern p prim ist und a nicht durch p teilbar ist. Hashfunktionen nutzen modulare Operationen, um große Eingaben auf feste Ausgaben abzubilden. Die ganzen Zahlen modulo n bilden einen vollständigen Ring, und falls n prim ist, sogar einen endlichen Körper.