Zum Inhalt springen

Modulo: Unterschied zwischen den Versionen

Aus FLBK-Wiki
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:
== Einführung ==
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.
Modulo (mod) ist eine mathematische Funktion, die den Rest aus einer Division zweier ganzer Zahlen bestimmt.  


Beispielrechnung:
==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


10 mod 3 = 1 (sprich: „zehn modulo drei ist gleich eins“)
:<math>a = k \cdot n + r \quad \text{und} \quad 0 \le r < n</math>


Denn 10 : 3 = 3, Rest 1
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'''.


(3 x 3 + 1 = 10)
* 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==
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) - "umlaufen".
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.


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) - "umlaufen".
===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


== Beispiel 12-Stunden Uhr ==
:<math>a \equiv b \pmod{n}</math>
[[Datei:Clock group.svg.png|mini]]
Eine bekannte Verwendung der modularen Arithmetik ist die 12-Stunden-Uhr, bei der der Tag in zwei 12-Stunden-Perioden unterteilt ist. Diese Zeitdarstellung ist vor allem in englischsprachigen Ländern üblich.  Hier gilt, wenn es 9:00 Uhr ist, ist es 4 Stunden später 1:00 Uhr. In zum Beispiel Deutschland würde die spätere Zeit 9 + 4 = 13 ergeben. Dies wäre für die 12-Stunden-Uhr nicht die richtige Lösung, da die Uhrzeit alle 12 Stunden "umläuft". Da die Stundenzahl nach Erreichen von 12 von vorne beginnt, kann diese Berechnung durch Modulo 12 abgebildet werden. 12 nicht nur mit 12 selbst, sondern auch mit 0 kongruent. Oder anders formulier; die als "12:00" bezeichnete Zeit kann auch als "0:00" bezeichnet werden.


<code>(9 + 4) modulo 12  = 13  modulo 12 = 1</code>
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.


== Implementierung ==
===Rechenregeln===
DIV- und MOD-Befehle bzw. Operatoren (für ganzzahlige Division und Restbildung) sind in den meisten Programmiersprachen (und sogar in CPUs) genau diesem Alltagsansatz entsprechend implementiert.
Beim Addieren, Subtrahieren und Multiplizieren darf man jederzeit zu den Resten übergehen, auch mitten in der Rechnung. Das Ergebnis ändert sich dadurch nicht:


Der Operator % (Prozentzeichen) dient in Java bei ganzen Zahlen dazu, den Divisionsrest zu ermitteln. Er kann für alle ganzzahligen Datentypen wie insbesondere int und long verwendet werden. Um beispielsweise den Divisionsrest von 50 durch 7 zu ermitteln, schreibt man "50 % 7".
:<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 ergibt mod(-7, 3) den Wert 2. Die Funktion remain(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 berechnet ModularExponent(a, x, n) die Potenz [math]\displaystyle{ a^x \bmod n }[/math]. In der deutschen Sprachversion heißt dieser Befehl ModulareExponentiation.

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

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]\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