Kryptologie/Restklassenring

Einleitung

In dieser Lerneinheit wollen wir zeigen, dass sich auf der Menge der Restklassen modulo $m$ ein Ring definieren lässt, den wir Restklassenring nennen. Wir benötigen dies um mit Restklassen in Kryptosystem, wie dem RSA-Kryptosystem, rechnen zu können und beispielsweise den erweiterten euklidischen Algorithmus anwenden zu können. Zu diesem Zweck benötigen wir die inneren Verknüpfungen der Addition und Multiplikation.

Restklassenring

Restklasse, $\mathbb {Z} /m\mathbb {Z}$, Ring, Halbgruppe, Gruppe, kommutative Gruppe, neutrales und inverses Element und Assoziativgesetz
$\mathbb {Z} /m\mathbb {Z}$
$\mathbb {Z} /m\mathbb {Z}$ ist die Menge aller Restklassen modulo $m$
Restklasse
Sei $a\in \mathbb {Z}$ modulo einer Zahl $m\in \mathbb {Z}$ die Menge aller ganzen Zahlen, die den gleichen Rest bei Division durch $m$ aufweisen wie $a$. Dann ist $[a]_{m}=\{b\in \mathbb {Z} \mid b\equiv a{\bmod {m}}\}$ die Restklasse zu $a$.
Ring
$(R,+,\cdot )$ heißt Ring, wenn für die Menge $R$ mit den zwei Verknüpfungen $+$ und $\cdot$ gilt $(R,+)$ eine kommutative Gruppe ist, $(R,\cdot )$ eine Halbgruppe ist, die Distributivgesetze gelten für alle $a,b,c\in R$, d.h. $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$
Halbgruppe
Eine Halbgruppe $H=(H,\circ )$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ \colon \,H\times H\to H,\,(a,b)\mapsto a\circ b,$ die assoziativ ist, d. h. für alle $a,b,c\in H$ gilt $a\circ (b\circ c)=(a\circ b)\circ c$.
Gruppe
Eine Halbgruppe $H$, die ein neutrales Element besitzt und jedes Element der Halbgruppe invertierbar ist, heißt Gruppe.
Kommutative Gruppe
Eine Gruppe $G$ heißt kommutative Gruppe, wenn die zugehörige Halbgruppe $H$ kommutativ ist, d.h. $a,b\in H$ gilt: $a\circ b=b\circ a$.
Neutrale Element
Sei $H=(H,\circ )$ eine Halbgruppe und $e\in H$. Wir nennen $e$ neutrales Element der Halbgruppe $H$, falls $e\circ a=a\circ e=a$ für alle $a\in H$.
Inverse Element
Sei $H=(H,\circ )$ eine Halbgruppe, $a,e\in H$ und $e$ das neutrale Element der Halbgruppe $H$. Wir nennen $b\in H$ das inverse Element bzw. die Inverse von $a$, falls gilt $a\circ b=b\circ a=e$.
Assoziativgesetz
Für alle $a,b,c\in G:a\circ \left(b\circ c\right)=\left(a\circ b\right)\circ c$.

Beweis Restklassenring

Wir wollen zeigen, dass die Menge der Restklassen einen Ring $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ darstellt. Wir müssen also zeigen:

• $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ ist eine kommutative Gruppe,
• $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ ist eine Halbgruppe,
• die Distributivgesetze $[a]_{m}\odot ([b]_{m}\oplus [c]_{m})=([a]_{m}\odot [b]_{m})\oplus ([a]_{m}\odot [c]_{m})$ und $([a]_{m}\oplus [b]_{m})\odot [c]_{m}=([a]_{m}\odot [c]_{m})\oplus ([b]_{m}\odot [c]_{m})$ gelten.

1. $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ ist eine kommutative Gruppe

Kommutative Gruppen sind nach Definition Gruppen, für die zusätzlich das Kommutativgesetz gilt. Wir zeigen also zuerst, dass

• $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ ist eine Gruppe,
• für $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ gilt das Kommutativgesetz.

1.1 $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ ist eine Gruppe

Nach Definition Gruppe ist $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ eine Gruppe, wenn

• für $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ gilt das Assoziativgesetz,
• $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ besitzt ein neutrales Element,
• $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ besitzt ein inverses Element.

1.1.1 Für $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ gilt das Assoziativgesetz

Nach Definition des Assoziativgesetzes muss gelten:

für alle $[a]_{m},[b]_{m},[c]_{m}\in \mathbb {Z} /m\mathbb {Z} :[a]_{m}\oplus ([b]_{m}\oplus [c]_{m})=([a]_{m}\oplus [b]_{m})\oplus [c]_{m}$.

Da wir die Addition $\oplus$ auf $\mathbb {Z} /m\mathbb {Z}$ schon definiert haben können wir die linke Seite der Gleichung umschreiben:

$[a]_{m}\oplus ([b]_{m}\oplus [c]_{m})$

$=[a]_{m}\oplus [b+c]_{m}$, Definition $\oplus$ in $\mathbb {Z} /m\mathbb {Z}$ angewandt

$=[a+(b+c)]_{m}$, Definition $\oplus$ in $\mathbb {Z} /m\mathbb {Z}$ angewandt

$=[(a+b)+c]_{m}$

$=[a+b]_{m}\oplus [c]_{m}$

$=([a]_{m}\oplus [b]_{m})\oplus [c]_{m}$

1.1.2 $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ besitzt ein neutrales Element

Neutrales Element
Neutrale Element
Sei $H=(H,\circ )$ eine Halbgruppe und $e\in H$. Wir nennen $e$ neutrales Element der Halbgruppe $H$, falls $e\circ a=a\circ e=a$ für alle $a\in H$.

Nach Definition des neutralen Elements muss gelten, dass es genau ein Element $e\in \mathbb {Z} /m\mathbb {Z}$, so dass für alle $[a]_{m}\in \mathbb {Z} /m\mathbb {Z}$ gilt: $[a]_{m}\oplus e=[a]_{m}$.

Hier ist $e=[0]_{m}$.

Analog zu 1.1.1 schreiben wir die linke Seite der Gleichung um:

$[a]_{m}\oplus e$

$=[a+0]_{m}$, in $\mathbb {Z}$ ist $0$ das neutrale Element

$=[a]_{m}$

(Somit ist $[0]_{m}$ das neutrale Element in $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$.)

Nun müssen wir noch zeigen, dass es genau ein neutrales Element gibt.

Wir beweisen dies durch Widerspruch.

Seien $e,e'\in \mathbb {Z} /m\mathbb {Z}$., dann gilt

$e\oplus e'=e$ und $e\oplus e'=e'$.

Darauf folgt jedoch

$e=e\oplus e'=e'$.

Bemerkung: Die hier verwendete Definition gilt nur für kommutative Gruppen, da nur in diesen gilt: $a\circ e=a=e\circ a$! Da wir gleich aber die Kommutativität von $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ zeigen werden, reicht es hier zu zeigen, dass $a\circ e=a$. Wir verweisen hiermit darauf, dass aufgrund der Kommutativität von $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ $[a]_{m}\oplus e=[a]_{m}=e\oplus [a]_{m}$ gilt. Analoges gilt für das inverse Element von $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$.

1.1.3 $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ besitzt ein inverses Element

Inverses und neutrales Element
Inverse Element
Sei $H=(H,\circ )$ eine Halbgruppe, $a,e\in H$ und $e$ das neutrale Element der Halbgruppe $H$. Wir nennen $b\in H$ das inverse Element bzw. die Inverse von $a$, falls gilt $a\circ b=b\circ a=e$.
Neutrale Element
Sei $H=(H,\circ )$ eine Halbgruppe und $e\in H$. Wir nennen $e$ neutrales Element der Halbgruppe $H$, falls $e\circ a=a\circ e=a$ für alle $a\in H$.

Nach Definition des neutralen Elements muss gelten, dass zu jedem $[a]_{m}\in \mathbb {Z} /m\mathbb {Z}$ gibt es genau ein $[a^{-1}]_{m}\in \mathbb {Z} /m\mathbb {Z}$ mit $[a]_{m}\oplus [a^{-1}]_{m}=e$.

Analog zu den 1.1.1 und 1.1.2 beginnen wir mit der linken Seite der Gleichung:

$[a]_{m}\oplus [a^{-1}]_{m}$

$=[a+a^{-1}]_{m}$, Definition $\oplus$ in $\mathbb {Z} /m\mathbb {Z}$ angewandt

$=[a+(-a)]_{m}$, in $\mathbb {Z}$ ist $-a$ das inverse Element zu $a$

$=[0]_{m}$, wie wir in 1.1.2 gezeigt haben, ist $[0]_{m}=e$ das neutrale Element

$=e$

Nun müssen wir noch zeigen, dass es genau inverses Element gibt.

Wir beweisen dies durch Widerspruch.

Seien $[a^{-1}]_{m},[a']_{m}\in \mathbb {Z} /m\mathbb {Z}$, dann gilt

$[a]_{m}\odot [a^{-1}]_{m}=e=[a]_{m}\odot [a']_{m}$.

Dann ist

$[a^{-1}]_{m}$

$=[a^{-1}]_{m}\odot e$

$=[a^{-1}]_{m}\odot ([a]_{m}\odot [a']_{m})$

$=([a^{-1}]_{m}\odot [a]_{m})\odot [a']_{m}$

$=e\odot [a']_{m}$

$=[a']_{m}$.

1.2 Für $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ gilt das Kommutativgesetz

Kommutative Gruppe
Kommutative Gruppe
Eine Gruppe $G$ heißt kommutative Gruppe, wenn die zugehörige Halbgruppe $H$ kommutativ ist, d.h. $a,b\in H$ gilt: $a\circ b=b\circ a$.

Nach dem Kommutativgesetzes muss gelten

Für alle $[a]_{m},[b]_{m}\in \mathbb {Z} /m\mathbb {Z}$ gilt: $[a]_{m}\oplus [b]_{m}=[b]_{m}\oplus [a]_{m}$.

Wir gehen analog zu den Beweisen in 1.1 vor:

$[a]_{m}\oplus [b]_{m}$

$=[a+b]_{m}$, Definition $\oplus$ in $\mathbb {Z} /m\mathbb {Z}$ angewandt

$=[b+a]_{m}$, $\mathbb {Z}$ ist kommutativ

$=[b]_{m}\oplus [a]_{m}$

Insgesamt haben wir mit 1.1 und 1.2 also nun gezeigt, dass $(\mathbb {Z} /m\mathbb {Z} ,\oplus )$ eine kommutative Gruppe ist ■

2. $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ ist eine Halbgruppe

Halbgruppe und Gruppe
Halbgruppe
Eine Halbgruppe $H=(H,\circ )$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ \colon \,H\times H\to H,\,(a,b)\mapsto a\circ b,$ die assoziativ ist, d. h. für alle $a,b,c\in H$ gilt $a\circ (b\circ c)=(a\circ b)\circ c$.
Gruppe
Eine Halbgruppe $H$, die ein neutrales Element besitzt und jedes Element der Halbgruppe invertierbar ist, heißt Gruppe.

Halbgruppen setzen, im Vergleich zur Definition der Gruppe, nur die Eigenschaft der Assoziativität voraus. Um zu zeigen, dass $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ eine Halbgruppe ist, reicht es daher die Assoziativität von $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ zu zeigen.

2.1 Assoziativität von $(\mathbb {Z} /m\mathbb {Z} ,\odot )$

Dies haben wir bereits in der Lernaufgabe der Seite (Halb-)Gruppen und Ringe gezeigt.

3. Distributivgesetze

Als letzten Schritt müssen nun noch zeigen, dass die die Distributivgesetze

$(1)$: $[a]_{m}\odot ([b]_{m}\oplus [c]_{m})=([a]_{m}\odot [b]_{m})\oplus ([a]_{m}\odot [c]_{m})$ und

$(2)$: $([a]_{m}\oplus [b]_{m})\odot [c]_{m}=([a]_{m}\odot [c]_{m})\oplus ([b]_{m}\odot [c]_{m})$

auf der Menge $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ gelten. Hier ist $e=[0]_{m}$.

Zu $(1)$:

Wir beginnen mit der linken Seite der Gleichung:

$[a]_{m}\odot ([b]_{m}\oplus [c]_{m})$

$=[a]_{m}\odot [b+c]_{m}$, nach Definition der Addition in $\mathbb {Z} /m\mathbb {Z}$

$=[a\cdot (b+c)]_{m}$, nach Definition der Multiplikation in $\mathbb {Z} /m\mathbb {Z}$

$=[a\cdot b+a\cdot c]_{m}$

$=[a\cdot b]_{m}\oplus [a\cdot c]_{m}$, nach Definition der Addition in $\mathbb {Z} /m\mathbb {Z}$

$=([a]_{m}\odot [b]_{m})\oplus ([a]_{m}\odot [c]_{m})$, nach Definition der Multiplikation in $\mathbb {Z} /m\mathbb {Z}$

Zu $(2)$:

Analog zu $(1)$:

Ring
Ring
$(R,+,\cdot )$ heißt Ring, wenn für die Menge $R$ mit den zwei Verknüpfungen $+$ und $\cdot$ gilt $(R,+)$ eine kommutative Gruppe ist, $(R,\cdot )$ eine Halbgruppe ist, die Distributivgesetze gelten für alle $a,b,c\in R$, d.h. $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$

$([a]_{m}\oplus [b]_{m})\odot [c]_{m}$

$=[a+b]_{m}\odot [c]_{m}$, nach Definition der Addition in $\mathbb {Z} /m\mathbb {Z}$

$=[(a+b)\cdot c]_{m}$, nach Definition der Multiplikation in $\mathbb {Z} /m\mathbb {Z}$

$=[a\cdot c+b\cdot c]_{m}$

$=[a\cdot c]_{m}\oplus [b\cdot c]_{m}$, nach Definition der Addition in $\mathbb {Z} /m\mathbb {Z}$

$=([a]_{m}\odot [c]_{m})\oplus ([b]_{m}\odot [c]_{m})$, nach Definition der Multiplikation in $\mathbb {Z} /m\mathbb {Z}$

Insgesamt haben wir somit gezeigt, dass $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ die Distributivgesetze erfüllt und dass $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ alle Bedingungen für einen Ring erfüllt. $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ ist somit ein Ring.■ Wir nennen diesen, aufgrund der Elemente der Menge, Restklassenring.

Multiplikative Inverse im Restklassenring $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$

Satz Multiplikative Inverse in $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$

Die Restklasse $[a]_{m}$ ist genau dann invertierbar in $\mathbb {Z} /m\mathbb {Z}$, wenn gilt $ggT(a,m)=1{\bmod {m}}$ und die Lösung $s\in [s]_{m}$ der Kongruenz $as\equiv 1{\bmod {m}}$ ist eindeutig bestimmt und wir nennen diese multiplikative Inverse von $[a]_{m}$.

Beweis Multiplikative Inverse in $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$

Kongruenz, Größte gemeinsame Teiler, Satz zu wichtigen Eigenschaften der Kongruenz und Lemma von Bézout
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Größte gemeinsame Teiler
Seien $a,b\in \mathbb {Z}$, wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d:=ggT(a,b)$ mit $d\in \mathbb {N}$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$, falls gilt: $(1)$: $d\mid a$ und $d\mid b$ und $(2)$: Für alle $c\in \mathbb {Z}$ mit $c\mid a$ und $c\mid b$ gilt: $c\leq d$.
Satz zu wichtige Eigenschaften der Kongruenz: $(2)$
Seien $a,b,c,d\in \mathbb {Z}$ und $m\in \mathbb {N}$. Es gilt: $a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}\Rightarrow$ $a+c\equiv b+d{\bmod {m}}$
Lemma von Bézout
Für alle $a,b\in \mathbb {Z}$ existieren $s,t\in \mathbb {Z}$, sodass gilt: $ggT(a,b)=s\cdot a+t\cdot b$.

Wir zeigen zunächst Hin- und Rückrichtung ohne die Eindeutigkeit ${\bmod {m}}$ zu zeigen.

Hinrichtung

Voraussetzung

Seien $d=ggT(a,m)$ und $s\in [s]_{m}$ eine Lösung der Kongruenz $as\equiv 1{\bmod {m}}$

Zu zeigen

$d=1$

Beweis

Nach der Definition des $ggT$ gilt $d\mid m$ und nach Definition der Kongruenz auch $d\mid (as-1)$.

Zusätzlich gilt, ebenfalls nach Definition des $ggT$, $d\mid a$ und es folgt nach Eigenschaft $(2)$ der Konruenz $d\mid -1$. Da $d\in \mathbb {N}$ nach Definition des $ggT$, ist $d=1$.

Rückrichtung

Voraussetzung

$d=1=ggT(a,m)$ und $[a]_{m}$ invertierter

Zu zeigen

$as\equiv 1{\bmod {m}}$ hat eine Lösung

Beweis

Nach dem Lemma von Bézout existieren Zahlen $s,t\in \mathbb {Z}$ mit

$1=a\cdot s+m\cdot t$

$\Leftrightarrow -mt=as-1$

Somit hat die Kongruenz $as\equiv 1{\bmod {m}}$ eine Lösung und $[s]_{m}$ ist das multiplikative Inverse zu $[a]_{m}$.

Eindeutigkeit

Voraussetzung

Sei $[s]_{m}$ das multiplikative Inverse zur Restklasse $[a]_{m}$ in $\mathbb {Z} /m\mathbb {Z}$ und es gilt $ggT(a,m)=1$

Zu zeigen

Das multiplikative Inverse zu $[a]_{m}$ ist in $\mathbb {Z} /m\mathbb {Z}$ eindeutig

Beweis

Wir nehmen an es existiert ein weiteres multiplikatives Inverses $[u]_{m}$ von $[a]_{m}$.

Es muss daher gelten $as\equiv au(\equiv 1){\bmod {m}}$ und es folgt nach der Kongruenz (hier ist $e=[0]_{m}$):

$m\mid (as-au)$

$\Leftrightarrow m\mid (a(s-u))$

Wegen $ggT(a,m)=1$ gilt $m\not \mid a$ und somit $m\mid (s-u)$.

Nach der Kongruenz folgt also

$m\mid (s-u)$

$\Leftrightarrow s\equiv u{\bmod {m}}$,

d.h. $u\in [s]_{m}$ und daher $[s]_{m}=[u]_{m}$■

Lernaufgabe

Bemerkung: Die folgenden Aufgaben sind wichtig, um den binomischen Lehrsatz in der Lerneinheit zum Satz von Euler anwenden zu können.

Aufgabe 1

Halbgruppe und neutrales Element
Halbgruppe
Eine Halbgruppe $H=(H,\circ )$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ \colon \,H\times H\to H,\,(a,b)\mapsto a\circ b,$ die assoziativ ist, d. h. für alle $a,b,c\in H$ gilt $a\circ (b\circ c)=(a\circ b)\circ c$.
Neutrale Element
Sei $H=(H,\circ )$ eine Halbgruppe und $e\in H$. Wir nennen $e$ neutrales Element der Halbgruppe $H$, falls $e\circ a=a\circ e=a$ für alle $a\in H$.

Beweisen Sie, dass die Halbgruppe $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ ein Monoid ist.

Sie benötigen zur Lösung folgende Definitionen:

Definition Monoid

Ein Monoid ist eine Halbgruppe mit links- und rechtsneutralem Element.

Definition links- und rechtsneutral

Sei $(M,\circ )$ eine Menge mit einer zweistelligen inneren Verknüpfung. Dann heißt ein Element $e\in M$

1. linksneutral, falls $e\circ a=a$ für alle $a\in M$ ist,
2. rechtsneutral, falls $a\circ e=a$ für alle $a\in M$ ist.

Lösung

Lösung Da wir bereits gezeigt haben, dass $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ eine Halbgruppe ist, reicht es zu zeigen, dass das neutrale Element links- und rechtsneutral ist. Wir müssen also nur zeigen, dass ein $[e]_{m}\in \mathbb {(} {\mathbb {Z} }/m\mathbb {Z} ,\odot )$ existiert, für das gilt linksneutral, also $[e]_{m}\odot [a]_{m}=[a]_{m}$ für alle $[a]_{m}\in (\mathbb {Z} /m\mathbb {Z} ,\odot )$, rechtsneutral, also $[a]_{m}\odot [e]_{m}=[a]_{m}$ für alle $[a]_{m}\in (\mathbb {Z} /m\mathbb {Z} ,\odot )$. Wir beginnen mit linksneutral: $[e]_{m}\odot [a]_{m}$ $=[e\cdot a]_{m}$, nach Definition Multiplikation in $\mathbb {Z} /m\mathbb {Z}$, $=[1\cdot a]_{m}$, da das neutrale Element der Multiplikation in $\mathbb {Z}$ die Zahl $1$ ist, ($=[1]_{m}\odot [a]_{m}$) $=[a]_{m}$ also ist $[e]_{m}=[1]_{m}$ linksneutral Nun folgt rechtsneutral: $[a]_{m}\odot [e]_{m}$ = $[a\cdot e]_{m}$, nach Definition Multiplikation in $\mathbb {Z} /m\mathbb {Z}$, $=[a\cdot 1]_{m}$, da das neutrale Element der Multiplikation in $\mathbb {Z}$ die Zahl $1$ ist, ($=[a]_{m}\odot [1]_{m}$) $=[a]_{m}$■

Aufgabe 2

Ring
Ring
$(R,+,\cdot )$ heißt Ring, wenn für die Menge $R$ mit den zwei Verknüpfungen $+$ und $\cdot$ gilt $(R,+)$ eine kommutative Gruppe ist, $(R,\cdot )$ eine Halbgruppe ist, die Distributivgesetze gelten für alle $a,b,c\in R$, d.h. $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$

Beweisen Sie, dass der Restklassenring kommutativ ist.

Sie benötigen zur Lösung folgende Definitionen:

Definition kommutativer Ring

Ein Ring heißt kommutativer Ring, falls er bezüglich der Multiplikation kommutativ ist.

Lösung

Lösung Auch wenn die Definition des kommutativen Rings sehr lang ist, so haben wir bereits gezeigt, dass $(\mathbb {Z} /m\mathbb {Z} ,\oplus ,\odot )$ ein Ring ist und in Aufgabe 1, dass die Halbgruppe $(\mathbb {Z} /m\mathbb {Z} ,\odot )$ ein Monoid ist, also das links- und rechtsneutrales Element $[1]_{m}$ besitzt. Es bleibt also nur noch zu zeigen, dass $[a]_{m}\odot [b]_{m}=[b]_{m}\odot [a]_{m}$ für alle $[a]_{m},[b]_{m}\in (\mathbb {Z} /m\mathbb {Z} ,\odot )$ gilt. Wir beginnen mit $[a]_{m}\odot [b]_{m}$ $=[a\cdot b]_{m}$ $=[b\cdot a]_{m}$ $=[b]_{m}\odot [a]_{m}$■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4.6: (Halb-)Gruppen und Ringe	4.7: Restklassenring	4: Caesar-Verschlüsselungsverfahren