Modulo: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Uhr-Beispiel, Tabellen, Beispiele für Hash und Netz, Potenz-Zyklus, Link zur Animation |
|||
| Zeile 1: | Zeile 1: | ||
==Schaubild== | == Schaubild == | ||
{{#drawio:modulo}} | {{#drawio:modulo}} | ||
'''Animation:''' [https://xinux.org/modulo.html Modulo: Rechnen im Kreis] | |||
= Modulo (Restklassenrechnung) = | = Modulo (Restklassenrechnung) = | ||
; Bedeutung | ; Bedeutung | ||
Die Modulo-Operation liefert den Rest einer Division. Sie ist ein zentrales | 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 == | == 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 == | == Beispielrechnungen == | ||
{| class="wikitable" | |||
! 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 und periodisches Verhalten == | ||
Modulo erzeugt immer einen Wertebereich zwischen 0 und n−1. | Modulo erzeugt immer einen Wertebereich zwischen '''0 und n−1'''. Beispiel für n = 5: | ||
Beispiel für n=5: | {| class="wikitable" | ||
! 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 == | == Anwendung in der Kryptografie == | ||
* RSA | Nimmt man eine Zahl immer wieder mal sich selbst und rechnet jedes Mal modulo, läuft auch das im Kreis. Beispiel mit n = 14: | ||
* Diffie-Hellman | {| class="wikitable" | ||
* ECC | ! Potenz !! 2<sup>1</sup> !! 2<sup>2</sup> !! 2<sup>3</sup> !! 2<sup>4</sup> !! 2<sup>5</sup> !! 2<sup>6</sup> !! 2<sup>7</sup> | ||
|- | |||
! 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. | |||
[[Kategorie:Kryptografie]] | [[Kategorie:Kryptografie]] | ||
Version vom 20. Oktober 2026, 05:29 Uhr
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.