Wir kommen nun zu einem ganz besonders wichtigen Ring, der in der Kryptografie eine zentrale Rolle spielt.
Sei \(n \in \mathbb{N}\) mit \(n \gt 1\). Wir haben bereits detailliert die Kongruent-Modulo-Äquivalenzrelation \(\sim_n\) und die Restklassen \([a] = \{a + kn|k \in \mathbb{Z}\}\) besprochen. Wir haben gesehen, dass \(\mathbb{Z} = [0] \cup [1] \cup \dots \cup [n-1]\) eine disjunkte Zerlegung von \(\mathbb{Z}\) bezüglich \(\sim_n\) ist. Ausgehend davon tätigen wir die folgende Definition.
Sei \(n \in \mathbb{N}\) mit \(n \gt 1\) und sei \(\sim_n\) die Kongruent-Modulo-Äquivalenzrelation. Dann definieren wir \(\mathbb{Z} / n\mathbb{Z} := \{[0], [1], \dots , [n-1]\}\). Ausgesprochen wird \(\mathbb{Z} / n\mathbb{Z}\) als "\(\mathbb{Z}\) modulo \(n\mathbb{Z}\)".
Die Elemente der Menge \(\mathbb{Z} / n\mathbb{Z}\) sind also die \(n\) disjunkten Restklassen \[[0] = \{0 + kn|k \in \mathbb{Z}\}\] \[[1] = \{1 + kn|k \in \mathbb{Z}\}\] \[\vdots\] \[[n-1] = \{n - 1 + kn|k \in \mathbb{Z}\}\]
Beispiel: \(\mathbb{Z}\) modulo \(n\mathbb{Z}\)
Ausgehend von dieser Definition wollen wir den sogenannten Restklassenring definieren. Dieser spielt in der Kryptografie eine entscheidende Rolle.
Für \([a], [b] \in \mathbb{Z} / n\mathbb{Z}\) sei \(+ : \mathbb{Z} / n\mathbb{Z} \times \mathbb{Z} / n\mathbb{Z} \rightarrow \mathbb{Z} / n\mathbb{Z}\) definiert durch \[[a] + [b] := [a + b]\] und \(\cdot : \mathbb{Z} / n\mathbb{Z} \times \mathbb{Z} / n\mathbb{Z} \rightarrow \mathbb{Z} / n\mathbb{Z}\) definiert durch \[[a] \cdot [b] := [a \cdot b]\]
Dann ist \((\mathbb{Z} / n\mathbb{Z}, +, \cdot)\) ein kommutativer Ring. Dieser Ring wird Restklassenring genannt.
Beweis:
Zunächst müssen wir zeigen, dass \(+\) und \(\cdot\) tatsächlich Verknüpfungen auf \(\mathbb{Z} / n\mathbb{Z}\) sind. Hierzu müssen \(+\) und \(\cdot\) wohldefiniert sein, d.h., die Ergebnisse der Operationen müssen unabhängig von der konkreten Wahl der Repräsentanten von \([a]\) und \([b]\) sein. Wir müssen zeigen, dass für \([a] = [a']\) und \([b] = [b']\) gilt, dass \([a + b] = [a' + b']\) und \([a \cdot b] = [a' \cdot b']\) ist.
Beweisen wir zunächst die Wohldefiniertheit der Addition:
Wegen \([a] = [a']\) ist \(a \sim_n a'\) und somit \(n|(a - a')\). Entsprechend gilt wegen \([b] = [b']\), dass \(b \sim_n b'\) und damit \(n|(b - b')\) ist. Damit gilt \(n|(a - a') + (b - b')\). Wegen \((a - a') + (b - b') = (a + b) - (a' + b')\) folgt ingesamt \(n|(a + b) - (a' + b')\) und damit \((a + b) \sim_n (a' + b')\). Es ist somit \([a + b] = [a' + b']\).
Die Addition ist somit unabhängig von der konkreten Wahl der Repräsentanten der Äquivalenzklassen definiert und damit wohldefiniert.
Ganz ähnlich zeigt man die Wohldefiniertheit der Multiplikation:
Wegen \([a] = [a']\) und \([b] = [b']\) folgt mit gleicher Argumentation wie oben, dass \(n|(a - a')\) und \(n|(b - b')\) ist. Damit gilt ebenfalls \(n|(a - a') \cdot b\) und \(n|(b - b') \cdot a\). Wegen \((a - a') \cdot b = a \cdot b - a' \cdot b\) und \((b - b') \cdot a' = a' \cdot b - a' \cdot b'\) gilt somit \(n|(a \cdot b\ - a' \cdot b)\) und \(n|(a' \cdot b\ - a' \cdot b')\). Damit teilt \(n\) insbesondere auch die Summe \((a \cdot b - a' \cdot b) + (a' \cdot b - a' \cdot b') = a \cdot b - a' \cdot b'\), also \(n|(a \cdot b - a' \cdot b')\). Daraus folgt \(a \cdot b \sim_n a' \cdot b'\) und damit \([a \cdot b] = [a' \cdot b']\).
Die Multiplikation ist somit ebenfalls unabhängig von der konkreten Wahl der Repräsentanten und damit wohldefiniert.
Insgesamt sind somit \(+\) und \(\cdot\) Verknüpfungen auf \(\mathbb{Z} / n\mathbb{Z}\). Es bleibt zu zeigen, dass die drei Eigenschaften von Ringen und das Kommutativgesetz gelten, d.h. wir müssen Folgendes zeigen:
Zu 1.:
Seien \([a], [b], [c] \in \mathbb{Z} / n\mathbb{Z}\). Dann gilt nach der obigen Definition der Addition und weil in \((\mathbb{Z}, +)\) das Assoziativgesetz gilt, Folgendes: \[[a] + ([b] + [c]) = [a] + [(b + c)]\] \[= [a + (b + c)]\] \[= [(a + b) + c]\] \[= [(a + b)] + [c]\] \[= ([a] + [b]) + [c]\] Die Addition ist also assoziativ.
Weiterhin gilt: \[[a] + [b] = [a + b]\] \[= [b + a]\] \[= [b] + [a]\] Die Addition ist somit auch kommutativ.
Wegen \[[a] + [0] = [a + 0]\] \[= [a]\] \[= [0 + a]\] \[= [0] + [a]\] ist \([0]\) das neutrale Element bezüglich \(+\) in \(\mathbb{Z} / n\mathbb{Z}\).
Wegen \[[a] + [-a] = [a + (-a)]\] \[= [a - a]\] \[= [0]\] \[= [(-a) + a]\] \[= [-a] + [a]\] besitzt jedes \([a] \in \mathbb{Z} / n\mathbb{Z}\) ein inverses Element \([-a] \in \mathbb{Z} / n\mathbb{Z}\) bezüglich \(+\) in \(\mathbb{Z} / n\mathbb{Z}\). Somit ist \((\mathbb{Z} / n\mathbb{Z}, +)\) eine abelsche Gruppe.
Zu 2.:
Seien \([a], [b], [c] \in \mathbb{Z} / n\mathbb{Z}\). Weil in \((\mathbb{Z}, \cdot)\) das Assoziativgesetz gilt, ist \[[a] \cdot ([b] \cdot [c]) = [a] \cdot [(b \cdot c)]\] \[= [a \cdot (b \cdot c)]\] \[= [(a \cdot b) \cdot c]\] \[= [(a \cdot b)] \cdot [c]\] \[= ([a] \cdot [b]) \cdot [c]\] Die Multiplikation ist also assoziativ.
Weiterhin ist wegen \[[a] \cdot [1] = [a \cdot 1]\] \[= [a]\] \[= [1 \cdot a]\] \[= [1] \cdot [a]\] \([1]\) das neutrale Element bezüglich \(\cdot\) in \(\mathbb{Z} / n\mathbb{Z}\). Somit ist \((\mathbb{Z} / n\mathbb{Z}, \cdot)\) eine Halbgruppe mit neutralem Element.
Zu 3.:
Seien \([a], [b], [c] \in \mathbb{Z} / n\mathbb{Z}\). Weil in \((\mathbb{Z}, \cdot)\) die Distributivgesetze gelten, folgt \[[a] \cdot ([b] + [c]) = [a] \cdot [(b + c)]\] \[= [a \cdot (b + c)]\] \[= [a \cdot b + a \cdot c]\] \[= [a \cdot b] + [a \cdot c]\] \[= [a] \cdot [b] + [a] \cdot [c]\] und \[([a] + [b]) \cdot [c] = [(a + b)] \cdot [c]\] \[= [(a + b) \cdot c]\] \[= [a \cdot c + b \cdot c]\] \[= [a \cdot c] + [b \cdot c]\] \[= [a] \cdot [c] + [b] \cdot [c]\] Somit gelten die Distributivgesetze für Ringe.
Zu 4.:
Seien \([a], [b] \in \mathbb{Z} / n\mathbb{Z}\). Wegen \[[a] \cdot [b] = [a \cdot b]\] \[= [b \cdot a]\] \[= [b] \cdot [a]\] folgt die Kommutativität.
Somit folgt insgesamt, dass \((\mathbb{Z} / n\mathbb{Z}, +, \cdot)\) ein kommutativer Ring ist. \(\square\)
Beispiel: Restklassenringe