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

Jeder rechnet täglich modulo, meist ohne es zu merken:

• Es ist 9 Uhr. In 5 Stunden ist es nicht 14 Uhr auf dem Zifferblatt, sondern 2 Uhr.
• Nach der 12 fängt der Zeiger wieder von vorn an.
• Genau das ist Modulo: 9 + 5 = 14, und 14 mod 12 = 2.

Auch beliebig viele Stunden passen auf die Uhr: 100 Stunden sind 8 volle Runden (96) und 4 Stunden übrig, also 100 mod 12 = 4.

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.