Modulo: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) Die Seite wurde neu angelegt: „== Einführung == Modulo (mod) ist eine mathematische Funktion, die den Rest aus einer Division zweier ganzer Zahlen bestimmt. Beispielrechnung: 10 mod 3 = 1 (sprich: „zehn modulo drei ist gleich eins“) Denn 10 : 3 = 3, Rest 1 (3 x 3 + 1 = 10) == Modulare Arithmetik == In der Mathematik ist die modulare Arithmetik ein Arithmetiksystem für ganze Zahlen, bei dem sich Zahlen bei Erreichen eines bestimmten Wertes - des Moduls (Pluralmodule) - "umla…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
Wie spät ist es fünf Stunden nach neun Uhr auf einer Uhr mit zwölf Stunden? Nicht vierzehn, sondern zwei. Dieses Rechnen „im Kreis“ heißt Rechnen modulo 12, und die Kryptologie baut fast alle ihre Verfahren darauf auf. | |||
==Definition== | |||
'''Modulo''' (kurz mod) ist eine Rechenoperation, die den Rest bei der Division zweier ganzer Zahlen liefert. Für eine ganze Zahl <math>a</math> und eine natürliche Zahl <math>n > 0</math> gibt es genau eine ganze Zahl <math>k</math> und genau einen Rest <math>r</math> mit | |||
:<math>a = k \cdot n + r \quad \text{und} \quad 0 \le r < n</math> | |||
Diese Zerlegung heißt '''Division mit Rest'''. Man schreibt <math>a \bmod n = r</math> und spricht „a modulo n ist gleich r“. Die Zahl <math>n</math> heißt '''Modul'''. | |||
* Der Rest liegt immer zwischen 0 und <math>n - 1</math>. | |||
* Ist <math>a \bmod n = 0</math>, dann ist <math>a</math> durch <math>n</math> teilbar. | |||
* Auch bei einer negativen Zahl <math>a</math> ist der Rest nicht negativ. Man addiert so oft <math>n</math>, bis das Ergebnis im Bereich von 0 bis <math>n - 1</math> liegt. | |||
== Modulare Arithmetik == | ==Modulare Arithmetik== | ||
Die modulare Arithmetik ist das Rechnen mit Resten. Die Zahlen „laufen um“: Nach <math>n - 1</math> geht es wieder mit 0 weiter, wie die Stunden auf dem Zifferblatt einer Uhr. | |||
===Kongruenz=== | |||
Zwei ganze Zahlen <math>a</math> und <math>b</math> heißen '''kongruent modulo''' <math>n</math>, wenn sie bei der Division durch <math>n</math> denselben Rest lassen. Man schreibt | |||
:<math>a \equiv b \pmod{n}</math> | |||
< | Gleichbedeutend ist: Die Differenz <math>a - b</math> ist durch <math>n</math> teilbar. Der Unterschied der Schreibweisen: <math>a \bmod n</math> ist eine Zahl, nämlich der Rest. <math>a \equiv b \pmod{n}</math> ist eine Aussage über zwei Zahlen. | ||
== | ===Rechenregeln=== | ||
Beim Addieren, Subtrahieren und Multiplizieren darf man jederzeit zu den Resten übergehen, auch mitten in der Rechnung. Das Ergebnis ändert sich dadurch nicht: | |||
:<math>(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n</math> | |||
:<math>(a - b) \bmod n = ((a \bmod n) - (b \bmod n)) \bmod n</math> | |||
:<math>(a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n</math> | |||
So bleiben die Zwischenergebnisse klein. Für die Division gilt keine solche Regel. An ihre Stelle tritt die Multiplikation mit dem [[Erweiterter euklidischer Algorithmus#Modulares Inverses|modularen Inversen]]. | |||
===Potenzen schrittweise berechnen=== | |||
Eine Potenz <math>a^x \bmod n</math> mit großem Exponenten rechnet man nicht zuerst aus, um dann zu teilen, denn <math>a^x</math> wird schnell riesig. Stattdessen multipliziert man Schritt für Schritt mit <math>a</math> und bildet nach jeder Multiplikation den Rest. Nach der Regel für das Produkt ist das erlaubt. | |||
Für große Exponenten ist auch das zu langsam. Dann hilft das wiederholte Quadrieren und Multiplizieren (siehe [[Square-and-Multiply]]). | |||
==Implementierung== | |||
In Java liefert der [[Operator#Arithmetische Operatoren|Operator]] <code>%</code> (Prozentzeichen) bei ganzen Zahlen den Rest der Division. Er lässt sich auf alle ganzzahligen [[Primitiver Datentyp|Datentypen]] anwenden, vor allem auf <code>int</code> und <code>long</code>. Den Rest von 50 bei der Division durch 7 berechnet der Ausdruck <code>50 % 7</code>. | |||
Bei negativen Zahlen weicht Java von der Definition oben ab: Das Ergebnis von <code>%</code> hat das Vorzeichen der ersten Zahl und kann deshalb negativ sein. Wer den Rest im Bereich von 0 bis <math>n - 1</math> braucht, addiert den Modul und bildet noch einmal den Rest: | |||
<syntaxhighlight lang="java"> | |||
public static int rest(int a, int n) { | |||
return ((a % n) + n) % n; | |||
} | |||
</syntaxhighlight> | |||
In der Kryptologie tritt der Fall beim Entschlüsseln auf, wenn ein Schlüssel abgezogen wird. | |||
==Rechnen mit dem Mathematiksystem== | |||
* '''TI-Nspire CX II:''' Die Funktion <code>mod(a, n)</code> liefert den Rest. Bei einem positiven Modul ist das Ergebnis nie negativ, zum Beispiel ergibt <code>mod(-7, 3)</code> den Wert 2. Die Funktion <code>remain(a, n)</code> übernimmt dagegen das Vorzeichen der ersten Zahl wie der Operator <code>%</code> in Java: <code>remain(-7, 3)</code> ergibt −1. | |||
* '''GeoGebra:''' Der Befehl <code>Mod(a, n)</code> liefert den Rest. In der CAS-Ansicht berechnet <code>ModularExponent(a, x, n)</code> die Potenz <math>a^x \bmod n</math>. In der deutschen Sprachversion heißt dieser Befehl <code>ModulareExponentiation</code>. | |||
Vorsicht bei großen Potenzen: Eine Zahl wie <math>7^{40}</math> hat 34 Stellen. Ein Mathematiksystem, das eine so große Zahl nur gerundet speichert, liefert danach einen falschen Rest. Sicher ist es, die Potenz schrittweise zu berechnen. | |||
Quellen: TI-Nspire CX Referenzhandbuch, Version 6.4; GeoGebra-Handbuch, Befehle Mod und ModularExponent; Stand November 2026. Weitere Hinweise zum Gerät stehen im Artikel [[Taschenrechner verwenden]]. | |||
==Beispiele== | |||
===Reste berechnen=== | |||
{| class="wikitable" style="text-align:center" | |||
! Aufgabe !! Division mit Rest !! Rest | |||
|- | |||
| <math>23 \bmod 5</math> || <math>23 = 4 \cdot 5 + 3</math> || <math>3</math> | |||
|- | |||
| <math>52 \bmod 26</math> || <math>52 = 2 \cdot 26 + 0</math> || <math>0</math> | |||
|- | |||
| <math>75 \bmod 7</math> || <math>75 = 10 \cdot 7 + 5</math> || <math>5</math> | |||
|- | |||
| <math>-4 \bmod 26</math> || <math>-4 = (-1) \cdot 26 + 22</math> || <math>22</math> | |||
|- | |||
| <math>-15 \bmod 12</math> || <math>-15 = (-2) \cdot 12 + 9</math> || <math>9</math> | |||
|} | |||
Bei den negativen Zahlen ist auch die ganze Zahl <math>k</math> vor dem Modul negativ. Nur so bleibt der Rest im Bereich von 0 bis <math>n - 1</math>. | |||
===Beispiel 12-Stunden Uhr=== | |||
[[Datei:Modulo Uhr.png|mini|Fünf Stunden nach 9 Uhr ist es 2 Uhr]] | |||
Auf einer Uhr mit zwölf Stunden beginnt die Zählung nach der Zwölf von vorn. Die Uhr rechnet modulo 12. Ist es 9 Uhr, dann ist es fünf Stunden später nicht 14 Uhr, sondern | |||
:<math>(9 + 5) \bmod 12 = 14 \bmod 12 = 2</math> | |||
Die Zwölf selbst entspricht dabei der Null, denn <math>12 \bmod 12 = 0</math>: 12 Uhr und 0 Uhr sind auf dieser Uhr dieselbe Stelle des Zifferblatts. Mit Kongruenzen geschrieben: <math>14 \equiv 2 \pmod{12}</math> und <math>12 \equiv 0 \pmod{12}</math>. | |||
===Mit Resten rechnen=== | |||
* Summe: <math>(19 + 12) \bmod 26 = 31 \bmod 26 = 5</math> | |||
* Produkt, zuerst die Faktoren verkleinert: <math>30 \bmod 26 = 4</math> und <math>55 \bmod 26 = 3</math>, also <math>(30 \cdot 55) \bmod 26 = (4 \cdot 3) \bmod 26 = 12</math> | |||
* Probe ohne Verkleinern: <math>30 \cdot 55 = 1650</math> und <math>1650 = 63 \cdot 26 + 12</math> | |||
===Potenz schrittweise berechnen=== | |||
Gesucht ist <math>3^{6} \bmod 11</math>. Die Potenzen werden der Reihe nach berechnet, nach jeder Multiplikation wird der Rest gebildet: | |||
:<math>3^{1} = 3</math> | |||
:<math>3^{2} \equiv 3 \cdot 3 = 9</math> | |||
:<math>3^{3} \equiv 9 \cdot 3 = 27 \equiv 5</math> | |||
:<math>3^{4} \equiv 5 \cdot 3 = 15 \equiv 4</math> | |||
:<math>3^{5} \equiv 4 \cdot 3 = 12 \equiv 1</math> | |||
:<math>3^{6} \equiv 1 \cdot 3 = 3</math> | |||
Also ist <math>3^{6} \bmod 11 = 3</math>. Das größte Zwischenergebnis war 27, obwohl <math>3^{6} = 729</math> ist. | |||
===Reste in Java berechnen=== | |||
Die Methode <code>rest</code> aus dem Abschnitt Implementierung und der Operator <code>%</code> im Vergleich: | |||
{| class="wikitable" | |||
! Ausdruck !! Ergebnis in Java !! Bemerkung | |||
|- | |||
| <code>50 % 7</code> || 1 || 50 = 7 · 7 + 1 | |||
|- | |||
| <code>-4 % 26</code> || -4 || negativ: Java übernimmt das Vorzeichen der ersten Zahl | |||
|- | |||
| <code>rest(-4, 26)</code> || 22 || der Rest, mit dem die Kryptologie rechnet | |||
|} | |||
[[Kategorie:Kryptologie]] | |||
[[Kategorie:Mathematik]] | |||
[[Kategorie:AHR I Informatik LK]] | |||
Aktuelle Version vom 15. November 2026, 07:57 Uhr
Wie spät ist es fünf Stunden nach neun Uhr auf einer Uhr mit zwölf Stunden? Nicht vierzehn, sondern zwei. Dieses Rechnen „im Kreis“ heißt Rechnen modulo 12, und die Kryptologie baut fast alle ihre Verfahren darauf auf.
Definition
Modulo (kurz mod) ist eine Rechenoperation, die den Rest bei der Division zweier ganzer Zahlen liefert. Für eine ganze Zahl [math]\displaystyle{ a }[/math] und eine natürliche Zahl [math]\displaystyle{ n > 0 }[/math] gibt es genau eine ganze Zahl [math]\displaystyle{ k }[/math] und genau einen Rest [math]\displaystyle{ r }[/math] mit
- [math]\displaystyle{ a = k \cdot n + r \quad \text{und} \quad 0 \le r < n }[/math]
Diese Zerlegung heißt Division mit Rest. Man schreibt [math]\displaystyle{ a \bmod n = r }[/math] und spricht „a modulo n ist gleich r“. Die Zahl [math]\displaystyle{ n }[/math] heißt Modul.
- Der Rest liegt immer zwischen 0 und [math]\displaystyle{ n - 1 }[/math].
- Ist [math]\displaystyle{ a \bmod n = 0 }[/math], dann ist [math]\displaystyle{ a }[/math] durch [math]\displaystyle{ n }[/math] teilbar.
- Auch bei einer negativen Zahl [math]\displaystyle{ a }[/math] ist der Rest nicht negativ. Man addiert so oft [math]\displaystyle{ n }[/math], bis das Ergebnis im Bereich von 0 bis [math]\displaystyle{ n - 1 }[/math] liegt.
Modulare Arithmetik
Die modulare Arithmetik ist das Rechnen mit Resten. Die Zahlen „laufen um“: Nach [math]\displaystyle{ n - 1 }[/math] geht es wieder mit 0 weiter, wie die Stunden auf dem Zifferblatt einer Uhr.
Kongruenz
Zwei ganze Zahlen [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] heißen kongruent modulo [math]\displaystyle{ n }[/math], wenn sie bei der Division durch [math]\displaystyle{ n }[/math] denselben Rest lassen. Man schreibt
- [math]\displaystyle{ a \equiv b \pmod{n} }[/math]
Gleichbedeutend ist: Die Differenz [math]\displaystyle{ a - b }[/math] ist durch [math]\displaystyle{ n }[/math] teilbar. Der Unterschied der Schreibweisen: [math]\displaystyle{ a \bmod n }[/math] ist eine Zahl, nämlich der Rest. [math]\displaystyle{ a \equiv b \pmod{n} }[/math] ist eine Aussage über zwei Zahlen.
Rechenregeln
Beim Addieren, Subtrahieren und Multiplizieren darf man jederzeit zu den Resten übergehen, auch mitten in der Rechnung. Das Ergebnis ändert sich dadurch nicht:
- [math]\displaystyle{ (a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n }[/math]
- [math]\displaystyle{ (a - b) \bmod n = ((a \bmod n) - (b \bmod n)) \bmod n }[/math]
- [math]\displaystyle{ (a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n }[/math]
So bleiben die Zwischenergebnisse klein. Für die Division gilt keine solche Regel. An ihre Stelle tritt die Multiplikation mit dem modularen Inversen.
Potenzen schrittweise berechnen
Eine Potenz [math]\displaystyle{ a^x \bmod n }[/math] mit großem Exponenten rechnet man nicht zuerst aus, um dann zu teilen, denn [math]\displaystyle{ a^x }[/math] wird schnell riesig. Stattdessen multipliziert man Schritt für Schritt mit [math]\displaystyle{ a }[/math] und bildet nach jeder Multiplikation den Rest. Nach der Regel für das Produkt ist das erlaubt.
Für große Exponenten ist auch das zu langsam. Dann hilft das wiederholte Quadrieren und Multiplizieren (siehe Square-and-Multiply).
Implementierung
In Java liefert der Operator % (Prozentzeichen) bei ganzen Zahlen den Rest der Division. Er lässt sich auf alle ganzzahligen Datentypen anwenden, vor allem auf int und long. Den Rest von 50 bei der Division durch 7 berechnet der Ausdruck 50 % 7.
Bei negativen Zahlen weicht Java von der Definition oben ab: Das Ergebnis von % hat das Vorzeichen der ersten Zahl und kann deshalb negativ sein. Wer den Rest im Bereich von 0 bis [math]\displaystyle{ n - 1 }[/math] braucht, addiert den Modul und bildet noch einmal den Rest:
public static int rest(int a, int n) {
return ((a % n) + n) % n;
}
In der Kryptologie tritt der Fall beim Entschlüsseln auf, wenn ein Schlüssel abgezogen wird.
Rechnen mit dem Mathematiksystem
- TI-Nspire CX II: Die Funktion
mod(a, n)liefert den Rest. Bei einem positiven Modul ist das Ergebnis nie negativ, zum Beispiel ergibtmod(-7, 3)den Wert 2. Die Funktionremain(a, n)übernimmt dagegen das Vorzeichen der ersten Zahl wie der Operator%in Java:remain(-7, 3)ergibt −1. - GeoGebra: Der Befehl
Mod(a, n)liefert den Rest. In der CAS-Ansicht berechnetModularExponent(a, x, n)die Potenz [math]\displaystyle{ a^x \bmod n }[/math]. In der deutschen Sprachversion heißt dieser BefehlModulareExponentiation.
Vorsicht bei großen Potenzen: Eine Zahl wie [math]\displaystyle{ 7^{40} }[/math] hat 34 Stellen. Ein Mathematiksystem, das eine so große Zahl nur gerundet speichert, liefert danach einen falschen Rest. Sicher ist es, die Potenz schrittweise zu berechnen.
Quellen: TI-Nspire CX Referenzhandbuch, Version 6.4; GeoGebra-Handbuch, Befehle Mod und ModularExponent; Stand November 2026. Weitere Hinweise zum Gerät stehen im Artikel Taschenrechner verwenden.
Beispiele
Reste berechnen
| Aufgabe | Division mit Rest | Rest |
|---|---|---|
| [math]\displaystyle{ 23 \bmod 5 }[/math] | [math]\displaystyle{ 23 = 4 \cdot 5 + 3 }[/math] | [math]\displaystyle{ 3 }[/math] |
| [math]\displaystyle{ 52 \bmod 26 }[/math] | [math]\displaystyle{ 52 = 2 \cdot 26 + 0 }[/math] | [math]\displaystyle{ 0 }[/math] |
| [math]\displaystyle{ 75 \bmod 7 }[/math] | [math]\displaystyle{ 75 = 10 \cdot 7 + 5 }[/math] | [math]\displaystyle{ 5 }[/math] |
| [math]\displaystyle{ -4 \bmod 26 }[/math] | [math]\displaystyle{ -4 = (-1) \cdot 26 + 22 }[/math] | [math]\displaystyle{ 22 }[/math] |
| [math]\displaystyle{ -15 \bmod 12 }[/math] | [math]\displaystyle{ -15 = (-2) \cdot 12 + 9 }[/math] | [math]\displaystyle{ 9 }[/math] |
Bei den negativen Zahlen ist auch die ganze Zahl [math]\displaystyle{ k }[/math] vor dem Modul negativ. Nur so bleibt der Rest im Bereich von 0 bis [math]\displaystyle{ n - 1 }[/math].
Beispiel 12-Stunden Uhr

Auf einer Uhr mit zwölf Stunden beginnt die Zählung nach der Zwölf von vorn. Die Uhr rechnet modulo 12. Ist es 9 Uhr, dann ist es fünf Stunden später nicht 14 Uhr, sondern
- [math]\displaystyle{ (9 + 5) \bmod 12 = 14 \bmod 12 = 2 }[/math]
Die Zwölf selbst entspricht dabei der Null, denn [math]\displaystyle{ 12 \bmod 12 = 0 }[/math]: 12 Uhr und 0 Uhr sind auf dieser Uhr dieselbe Stelle des Zifferblatts. Mit Kongruenzen geschrieben: [math]\displaystyle{ 14 \equiv 2 \pmod{12} }[/math] und [math]\displaystyle{ 12 \equiv 0 \pmod{12} }[/math].
Mit Resten rechnen
- Summe: [math]\displaystyle{ (19 + 12) \bmod 26 = 31 \bmod 26 = 5 }[/math]
- Produkt, zuerst die Faktoren verkleinert: [math]\displaystyle{ 30 \bmod 26 = 4 }[/math] und [math]\displaystyle{ 55 \bmod 26 = 3 }[/math], also [math]\displaystyle{ (30 \cdot 55) \bmod 26 = (4 \cdot 3) \bmod 26 = 12 }[/math]
- Probe ohne Verkleinern: [math]\displaystyle{ 30 \cdot 55 = 1650 }[/math] und [math]\displaystyle{ 1650 = 63 \cdot 26 + 12 }[/math]
Potenz schrittweise berechnen
Gesucht ist [math]\displaystyle{ 3^{6} \bmod 11 }[/math]. Die Potenzen werden der Reihe nach berechnet, nach jeder Multiplikation wird der Rest gebildet:
- [math]\displaystyle{ 3^{1} = 3 }[/math]
- [math]\displaystyle{ 3^{2} \equiv 3 \cdot 3 = 9 }[/math]
- [math]\displaystyle{ 3^{3} \equiv 9 \cdot 3 = 27 \equiv 5 }[/math]
- [math]\displaystyle{ 3^{4} \equiv 5 \cdot 3 = 15 \equiv 4 }[/math]
- [math]\displaystyle{ 3^{5} \equiv 4 \cdot 3 = 12 \equiv 1 }[/math]
- [math]\displaystyle{ 3^{6} \equiv 1 \cdot 3 = 3 }[/math]
Also ist [math]\displaystyle{ 3^{6} \bmod 11 = 3 }[/math]. Das größte Zwischenergebnis war 27, obwohl [math]\displaystyle{ 3^{6} = 729 }[/math] ist.
Reste in Java berechnen
Die Methode rest aus dem Abschnitt Implementierung und der Operator % im Vergleich:
| Ausdruck | Ergebnis in Java | Bemerkung |
|---|---|---|
50 % 7 |
1 | 50 = 7 · 7 + 1 |
-4 % 26 |
-4 | negativ: Java übernimmt das Vorzeichen der ersten Zahl |
rest(-4, 26) |
22 | der Rest, mit dem die Kryptologie rechnet |