Restklassen-Multiplikation

Ein Film dauert 5 Stunden – und du schaust ihn 5 -mal hintereinander. Wo steht der Stundenzeiger danach, wenn du um 0 Uhr anfängst? 5 cdot 5 = 25 Stunden, auf der Uhr also 1 Uhr. Modulo 12 gilt: 5 cdot 5 = 1 . So wie man Restklassen-Addition|Restklassen addieren kann, kann man sie auch multiplizieren . Das Spannende: Manchmal gibt es dann zu einer Zahl ein „Kehrwert“-Gegenstück, obwohl man gar keine Brüche benutzt. Genau das steckt in der RSA-Verschlüsselung. Definition (a + m mathbb{Z}) cdot (b + m mathbb{Z}) = a cdot b + m mathbb{Z} qquad text{kurz:} qquad overline{a} cdot overline{b} = overline{a cdot b} Also: Repräsentanten malnehmen , dann bmod m rechnen. Das Ergebnis hängt nicht von der Wahl der Repräsentanten ab. Multiplikationstafeln im Vergleich mathbb{Z} 5 (Modul ist Primzahl): | cdot | overline{1} | overline{2} | overline{3} | overline{4} | |---|---|---|---|---| | overline{1} | overline{1} | overline{2} | overline{3} | overline{4} | | overline{2} | overline{2} | overline{4} | overline{1} | overline{3} | | overline{3} | overline{3} | overline{1} | overline{4} | overline{2} | | overline{4} | overline{4} | overline{3} | overline{2} | overline{1} | In jeder Zeile steht einmal overline{1} – jede Klasse hat ein Inverses. mathbb{Z} 6 (Modul keine Primzahl), Ausschnitt: | cdot | overline{1} | overline{2} | overline{3} | overline{4} | overline{5} | |---|---|---|---|---|---| | overline{2} | overline{2} | overline{4} | overline{0} | overline{2} | overline{4} | | overline{5} |

Worum geht's?

Ein Film dauert 5 5 5 Stunden – und du schaust ihn 5 5 5 -mal hintereinander. Wo steht der Stundenzeiger danach, wenn du um 0 0 0 Uhr anfängst? 5 ⋅ 5 = 25 5 \cdot 5 = 25 5 ⋅ 5 = 25 Stunden, auf der Uhr also 1 1 1 Uhr. Modulo 12 12 12 gilt: 5 ⋅ 5 = 1 5 \cdot 5 = 1 5 ⋅ 5 = 1 . So wie man Restklassen addieren kann, kann man sie auch multiplizieren . Das Spannende: Manchmal gibt es dann zu einer Zahl ein „Kehrwert“-Gegenstück, obwohl man gar keine Brüche benutzt. Genau das steckt in der RSA-Verschlüsselung.

Formel mit Erklärung

Definition ( a + m Z ) ⋅ ( b + m Z ) = a ⋅ b + m Z kurz: a ‾ ⋅ b ‾ = a ⋅ b ‾ (a + m\mathbb{Z}) \cdot (b + m\mathbb{Z}) = a \cdot b + m\mathbb{Z} \qquad\text{kurz:}\qquad \overline{a} \cdot \overline{b} = \overline{a \cdot b} ( a + m Z ) ⋅ ( b + m Z ) = a ⋅ b + m Z kurz: a ⋅ b = a ⋅ b Also: Repräsentanten malnehmen , dann   m o d   m \bmod m mod m rechnen. Das Ergebnis hängt nicht von der Wahl der Repräsentanten ab. Multiplikationstafeln im Vergleich Z 5 \mathbb{Z}_5 Z 5 ​ (Modul ist Primzahl): ⋅ \cdot ⋅ 1 ‾ \overline{1} 1 2 ‾ \overline{2} 2 3 ‾ \overline{3} 3 4 ‾ \overline{4} 4 1 ‾ \overline{1} 1 1 ‾ \overline{1} 1 2 ‾ \overline{2} 2 3 ‾ \overline{3} 3 4 ‾ \overline{4} 4 2 ‾ \overline{2} 2 2 ‾ \overline{2} 2 4 ‾ \overline{4} 4 1 ‾ \overline{1} 1 3 ‾ \overline{3} 3 3 ‾ \overline{3} 3 3 ‾ \overline{3} 3 1 ‾ \overline{1} 1 4 ‾ \overline{4} 4 2 ‾ \overline{2} 2 4 ‾ \overline{4} 4 4 ‾ \overline{4} 4 3 ‾ \overline{3} 3 2 ‾ \overline{2} 2 1 ‾ \overline{1} 1 In jeder Zeile steht einmal 1 ‾ \overline{1} 1 – jede Klasse hat ein Inverses. Z 6 \mathbb{Z}_6 Z 6 ​ (Modul keine Primzahl), Ausschnitt: ⋅ \cdot ⋅ 1 ‾ \overline{1} 1 2 ‾ \overline{2} 2 3 ‾ \overline{3} 3 4 ‾ \overline{4} 4 5 ‾ \overline{5} 5 2 ‾ \overline{2} 2 2 ‾ \overline{2} 2 4 ‾ \overline{4} 4 0 ‾ \overline{0} 0 2 ‾ \overline{2} 2 4 ‾ \overline{4} 4 5 ‾ \overline{5} 5 5 ‾ \overline{5} 5 4 ‾ \overline{4} 4 3 ‾ \overline{3} 3 2 ‾ \overline{2} 2 1 ‾ \overline{1} 1 Achtung: 2 ‾ ⋅ 3 ‾ = 0 ‾ \overline{2} \cdot \overline{3} = \overline{0} 2 ⋅ 3 = 0 , obwohl keiner der Faktoren 0 ‾ \overline{0} 0 ist. Und 2 ‾ \overline{2} 2 hat kein Inverses (keine 1 ‾ \overline{1} 1 in der Zeile). Inverses Element a ‾ \overline{a} a hat genau dann ein Inverses a ‾ − 1 \overline{a}^{-1} a − 1 mit a ‾ ⋅ a ‾ − 1 = 1 ‾ \overline{a} \cdot \overline{a}^{-1} = \overline{1} a ⋅ a − 1 = 1 , wenn ggT ( a , m ) = 1 \text{ggT}(a, m) = 1 ggT ( a , m ) = 1 ist. Solche Klassen heißen prime Restklassen . Das Inverse findet man durch Probieren oder mit dem erweiterten euklidischen Algorithmus . Die primen Restklassen bilden mit der Multiplikation eine kommutative Gruppe ( Z m ∗ , ⋅ ) (\mathbb{Z}_m^*, \cdot) ( Z m ∗ ​ , ⋅ ) mit neutralem Element 1 ‾ \overline{1} 1 (siehe Menge der primen Restklassen ).

Beispiele

Leicht#1
Berechne ( 5 + 6 Z ) ⋅ ( 2 + 6 Z ) (5 + 6\mathbb{Z}) \cdot (2 + 6\mathbb{Z}) ( 5 + 6 Z ) ⋅ ( 2 + 6 Z ) . ( 5 + 6 Z ) ⋅ ( 2 + 6 Z ) = 10 + 6 Z = 4 + 6 Z (5 + 6\mathbb{Z}) \cdot (2 + 6\mathbb{Z}) = 10 + 6\mathbb{Z} = 4 + 6\mathbb{Z} ( 5 + 6 Z ) ⋅ ( 2 + 6 Z ) = 10 + 6 Z = 4 + 6 Z denn 10 = 1 ⋅ 6 + 4 10 = 1 \cdot 6 + 4 10 = 1 ⋅ 6 + 4 .

Zusammenfassung

Restklassen multipliziert man über ihre Repräsentanten: a ‾ ⋅ b ‾ = a ⋅ b ‾ \overline{a} \cdot \overline{b} = \overline{a \cdot b} a ⋅ b = a ⋅ b , danach   m o d   m \bmod m mod m . a ‾ \overline{a} a hat ein Inverses genau dann, wenn ggT ( a , m ) = 1 \text{ggT}(a, m) = 1 ggT ( a , m ) = 1 . Inverse findet man durch Probieren oder mit dem erweiterten euklidischen Algorithmus. Ist m m m keine Primzahl, kann ein Produkt 0 ‾ \overline{0} 0 sein, ohne dass ein Faktor 0 ‾ \overline{0} 0 ist. Die primen Restklassen bilden mit ⋅ \cdot ⋅ eine kommutative Gruppe mit neutralem Element 1 ‾ \overline{1} 1 .

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: