Modulo

Schaubild

Animation: Modulo: Rechnen im Kreis

Modulo (Restklassenrechnung)

Bedeutung

Die Modulo-Operation liefert den Rest einer Division. Sie ist ein zentrales Werkzeug in der Kryptografie, der Informatik und bei Netzwerkberechnungen.

Die Uhr und das Band

Man stelle sich eine ganz normale Uhr mit 12 Stunden vor und ein Band, auf dem Stunden abgetragen sind. Das Band wird ab der 12 um die Uhr gewickelt.

• Ein Band mit 14 Stunden reicht einmal ganz herum, 2 Stunden stehen über: 14 mod 12 = 2.
• Ein Band mit 29 Stunden reicht zweimal ganz herum (24), 5 Stunden stehen über: 29 mod 12 = 5.

Wie oft das Band herumgeht, interessiert nicht. Das Ergebnis von Modulo ist der Überstand.

Grundprinzip

a mod n = r

• r ist der Rest, der entsteht, wenn a durch n geteilt wird.
• Man kann sich eine Uhr mit n Feldern vorstellen, beschriftet mit 0 bis n−1.
• Der Zeiger läuft a Schritte. Wo er stehen bleibt, ist das Ergebnis.
• Wie viele volle Runden er dabei gedreht hat, spielt keine Rolle.

Beispielrechnungen

Rechnung	als Division	auf der Uhr
17 mod 5 = 2	17 / 5 = 3 Rest 2	3 volle Runden, 2 Schritte übrig
29 mod 7 = 1	29 / 7 = 4 Rest 1	4 volle Runden, 1 Schritt übrig
100 mod 10 = 0	100 / 10 = 10 Rest 0	genau 10 Runden, der Zeiger steht wieder auf 0

Geht eine Division ohne Rest auf, ist das Ergebnis 0.

Modulo und periodisches Verhalten

Modulo erzeugt immer einen Wertebereich zwischen 0 und n−1. Beispiel für n = 5:

a	0	1	2	3	4	5	6	7	8	9	10	11
a mod 5	0	1	2	3	4	0	1	2	3	4	0	1

Zählt man hoch, kommen die Ergebnisse immer in derselben Reihenfolge wieder. Dadurch entstehen wiederkehrende Muster: Die Uhr läuft im Kreis.

Warum Modulo wichtig ist

• Kryptografie: Modulo erzeugt Zyklen, die sich für Schlüsselräume und mathematische Gruppen eignen (RSA, Diffie-Hellman, ECC).
• Hashfunktionen und Prüfsummen: Modulo bringt beliebig große Werte in einen festen Bereich. Beispiel: Ein Hashwert 1 234 567 soll auf eine Tabelle mit 8 Fächern verteilt werden: 1 234 567 mod 8 = 7, also Fach 7.
• Netzwerke: Modulo hilft, Bereiche zu adressieren. Beispiel: Wo liegt 10.0.0.77 in Blöcken zu 64 Adressen (/26)? 77 mod 64 = 13, also Host 13 im Block, der Block beginnt bei 77 − 13 = 64, das Netz ist 10.0.0.64/26.

Anwendung in der Kryptografie

Nimmt man eine Zahl immer wieder mal sich selbst und rechnet jedes Mal modulo, läuft auch das im Kreis. Beispiel mit n = 14:

Potenz	21	22	23	24	25	26	27
mod 14	2	4	8	2	4	8	2

Auf solchen Zyklen beruhen die asymmetrischen Verfahren, nur mit Zahlen, die Hunderte Stellen lang sind:

• RSA rechnet „hoch, dann mod n“ mit n = p · q aus zwei großen Primzahlen, siehe RSA Beispiel (dort mit n = 14).
• Diffie-Hellman rechnet „g hoch a, dann mod p“ in einer zyklischen Gruppe.
• ECC rechnet auf einer elliptischen Kurve modulo einer Primzahl.

Allen gemeinsam: Vorwärts ist die Rechnung leicht, rückwärts kommt man ohne das Geheimnis praktisch nicht hin.