Kryptologie/Restklassenring: Unterschied zwischen den Versionen

Aktuelle Version vom 22. April 2020, 18:44 Uhr

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^[1] und beispielsweise den erweiterten euklidischen Algorithmus anwenden zu können^[2]. Zu diesem Zweck benötigen wir die inneren Verknüpfungen der Addition und Multiplikation^[3].

Restklassenring

Restklasse, $ℤ / m ℤ$ , Ring, Halbgruppe, Gruppe, kommutative Gruppe, neutrales und inverses Element und Assoziativgesetz
$ℤ / m ℤ$
$ℤ / m ℤ$ ist die Menge aller Restklassen modulo $m$ ^[4]
Restklasse
Sei $a \in ℤ$ modulo einer Zahl $m \in ℤ$ die Menge aller ganzen Zahlen, die den gleichen Rest bei Division durch $m$ aufweisen wie $a$ . Dann ist $[a]_{m} = {b \in ℤ ∣ b \equiv a mod m}$ die Restklasse zu $a$ ^[5].
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)$ ^[6]
Halbgruppe
Eine Halbgruppe $H = (H, \circ)$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ : 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$ ^[7]^[3].
Gruppe
Eine Halbgruppe $H$ , die ein neutrales Element besitzt und jedes Element der Halbgruppe invertierbar ist, heißt Gruppe^[8].
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$ ^[9].
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$ ^[8].
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$ ^[8].
Assoziativgesetz
Für alle $a, b, c \in G : a \circ (b \circ c) = (a \circ b) \circ c$ ^[6].

Beweis Restklassenring

Wir wollen zeigen, dass die Menge der Restklassen einen Ring $(ℤ / m ℤ, \oplus, ⊙)$ darstellt. Wir müssen also zeigen:

$(ℤ / m ℤ, \oplus)$ ist eine kommutative Gruppe,
$(ℤ / m ℤ, ⊙)$ ist eine Halbgruppe,
die Distributivgesetze $[a]_{m} ⊙ ([b]_{m} \oplus [c]_{m}) = ([a]_{m} ⊙ [b]_{m}) \oplus ([a]_{m} ⊙ [c]_{m})$ und $([a]_{m} \oplus [b]_{m}) ⊙ [c]_{m} = ([a]_{m} ⊙ [c]_{m}) \oplus ([b]_{m} ⊙ [c]_{m})$ gelten^[6].

1. $(ℤ / m ℤ, \oplus)$ ist eine kommutative Gruppe

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

$(ℤ / m ℤ, \oplus)$ ist eine Gruppe,
für $(ℤ / m ℤ, \oplus)$ gilt das Kommutativgesetz^[10].

1.1 $(ℤ / m ℤ, \oplus)$ ist eine Gruppe

Nach Definition Gruppe ist $(ℤ / m ℤ, \oplus)$ eine Gruppe, wenn

für $(ℤ / m ℤ, \oplus)$ gilt das Assoziativgesetz,
$(ℤ / m ℤ, \oplus)$ besitzt ein neutrales Element,
$(ℤ / m ℤ, \oplus)$ besitzt ein inverses Element^[9].

1.1.1 Für $(ℤ / m ℤ, \oplus)$ gilt das Assoziativgesetz

Nach Definition des Assoziativgesetzes muss gelten:

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

Da wir die Addition $\oplus$ auf $ℤ / m ℤ$ 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 $ℤ / m ℤ$ angewandt

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

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

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

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

1.1.2 $(ℤ / m ℤ, \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$ ^[8].

Nach Definition des neutralen Elements muss gelten, dass es genau ein Element $e \in ℤ / m ℤ$ , so dass für alle $[a]_{m} \in ℤ / m ℤ$ 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 $ℤ$ ist $0$ das neutrale Element^[11]

$= [a]_{m}$ ^[11]

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

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

Wir beweisen dies durch Widerspruch.

Seien $e, e^{'} \in ℤ / m ℤ$ ., dann gilt

$e \oplus e^{'} = e$ und $e \oplus e^{'} = e^{'}$ .

Darauf folgt jedoch

$e = e \oplus e^{'} = e^{'}$ ^[12].

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

1.1.3 $(ℤ / m ℤ, \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$ ^[8].
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$ ^[8].

Nach Definition des neutralen Elements muss gelten, dass zu jedem $[a]_{m} \in ℤ / m ℤ$ gibt es genau ein $[a^{- 1}]_{m} \in ℤ / m ℤ$ 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 $ℤ / m ℤ$ angewandt

$= [a + (- a)]_{m}$ , in $ℤ$ ist $- a$ das inverse Element zu $a$ ^[13]^[11]

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

$= e$ ^[11]

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

Wir beweisen dies durch Widerspruch.

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

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

Dann ist

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

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

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

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

$= e ⊙ [a^{'}]_{m}$

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

1.2 Für $(ℤ / m ℤ, \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$ ^[9].

Nach dem Kommutativgesetzes muss gelten

Für alle $[a]_{m}, [b]_{m} \in ℤ / m ℤ$ 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 $ℤ / m ℤ$ angewandt

$= [b + a]_{m}$ , $ℤ$ ist kommutativ

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

Insgesamt haben wir mit 1.1 und 1.2 also nun gezeigt, dass $(ℤ / m ℤ, \oplus)$ eine kommutative Gruppe ist ■^[9]

2. $(ℤ / m ℤ, ⊙)$ ist eine Halbgruppe

Halbgruppe und Gruppe
Halbgruppe
Eine Halbgruppe $H = (H, \circ)$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ : 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$ ^[7]^[3].
Gruppe
Eine Halbgruppe $H$ , die ein neutrales Element besitzt und jedes Element der Halbgruppe invertierbar ist, heißt Gruppe^[8].

Halbgruppen setzen, im Vergleich zur Definition der Gruppe, nur die Eigenschaft der Assoziativität voraus. Um zu zeigen, dass $(ℤ / m ℤ, ⊙)$ eine Halbgruppe ist, reicht es daher die Assoziativität von $(ℤ / m ℤ, ⊙)$ zu zeigen^[3].

2.1 Assoziativität von $(ℤ / m ℤ, ⊙)$

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} ⊙ ([b]_{m} \oplus [c]_{m}) = ([a]_{m} ⊙ [b]_{m}) \oplus ([a]_{m} ⊙ [c]_{m})$ und

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

auf der Menge $(ℤ / m ℤ, \oplus, ⊙)$ gelten^[14]. Hier ist $e = [0]_{m}$ .

Zu $(1)$ :

Wir beginnen mit der linken Seite der Gleichung:

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

$= [a]_{m} ⊙ [b + c]_{m}$ , nach Definition der Addition in $ℤ / m ℤ$

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

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

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

$= ([a]_{m} ⊙ [b]_{m}) \oplus ([a]_{m} ⊙ [c]_{m})$ , nach Definition der Multiplikation in $ℤ / m ℤ$ ^[15]

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)$ ^[6]

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

$= [a + b]_{m} ⊙ [c]_{m}$ , nach Definition der Addition in $ℤ / m ℤ$

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

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

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

$= ([a]_{m} ⊙ [c]_{m}) \oplus ([b]_{m} ⊙ [c]_{m})$ , nach Definition der Multiplikation in $ℤ / m ℤ$ ^[15]

Insgesamt haben wir somit gezeigt, dass $(ℤ / m ℤ, \oplus, ⊙)$ die Distributivgesetze erfüllt und dass $(ℤ / m ℤ, \oplus, ⊙)$ alle Bedingungen für einen Ring erfüllt. $(ℤ / m ℤ, \oplus, ⊙)$ ist somit ein Ring.■ Wir nennen diesen, aufgrund der Elemente der Menge, Restklassenring^[14].

Multiplikative Inverse im Restklassenring $(ℤ / m ℤ, \oplus, ⊙)$

Satz Multiplikative Inverse in $(ℤ / m ℤ, \oplus, ⊙)$

Die Restklasse $[a]_{m}$ ist genau dann invertierbar in $ℤ / m ℤ$ , wenn gilt $g g T (a, m) = 1 mod m$ und die Lösung $s \in [s]_{m}$ der Kongruenz $a s \equiv 1 mod m$ ist eindeutig bestimmt und wir nennen diese multiplikative Inverse von $[a]_{m}$ ^[16].

Beweis Multiplikative Inverse in $(ℤ / m ℤ, \oplus, ⊙)$

Kongruenz, Größte gemeinsame Teiler, Satz zu wichtigen Eigenschaften der Kongruenz und Lemma von Bézout
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[17].
Größte gemeinsame Teiler
Seien $a, b \in ℤ$ , wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d : = g g T (a, b)$ mit $d \in ℕ$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$ , falls gilt: $(1)$ : $d ∣ a$ und $d ∣ b$ und $(2)$ : Für alle $c \in ℤ$ mit $c ∣ a$ und $c ∣ b$ gilt: $c \leq d$ ^[18].
Satz zu wichtige Eigenschaften der Kongruenz: $(2)$
Seien $a, b, c, d \in ℤ$ und $m \in ℕ$ . Es gilt: $a \equiv b mod m$ und $c \equiv d mod m \Rightarrow$ $a + c \equiv b + d mod m$ ^[19]
Lemma von Bézout
Für alle $a, b \in ℤ$ existieren $s, t \in ℤ$ , sodass gilt: $g g T (a, b) = s \cdot a + t \cdot b$ ^[20]^[21].

Wir zeigen zunächst Hin- und Rückrichtung ohne die Eindeutigkeit $mod m$ zu zeigen.

Hinrichtung

Voraussetzung

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

Zu zeigen

$d = 1$

Beweis

Nach der Definition des $g g T$ gilt $d ∣ m$ und nach Definition der Kongruenz auch $d ∣ (a s - 1)$ .

Zusätzlich gilt, ebenfalls nach Definition des $g g T$ , $d ∣ a$ und es folgt nach Eigenschaft $(2)$ der Konruenz $d ∣ - 1$ . Da $d \in ℕ$ nach Definition des $g g T$ , ist $d = 1$ .

Rückrichtung

Voraussetzung

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

Zu zeigen

$a s \equiv 1 mod m$ hat eine Lösung

Beweis

Nach dem Lemma von Bézout existieren Zahlen $s, t \in ℤ$ mit

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

$\Leftrightarrow - m t = a s - 1$

Somit hat die Kongruenz $a s \equiv 1 mod 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 $ℤ / m ℤ$ und es gilt $g g T (a, m) = 1$

Zu zeigen

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

Beweis

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

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

$m ∣ (a s - a u)$

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

Wegen $g g T (a, m) = 1$ gilt $m ∤ a$ und somit $m ∣ (s - u)$ .

Nach der Kongruenz folgt also

$m ∣ (s - u)$

$\Leftrightarrow s \equiv u mod m$ ,

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

Lernaufgabe

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

Aufgabe 1

Halbgruppe und neutrales Element
Halbgruppe
Eine Halbgruppe $H = (H, \circ)$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ : 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$ ^[7]^[3].
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$ ^[8].

Beweisen Sie, dass die Halbgruppe $(ℤ / m ℤ, ⊙)$ ein Monoid ist.

Sie benötigen zur Lösung folgende Definitionen:

Definition Monoid

Ein Monoid ist eine Halbgruppe mit links- und rechtsneutralem Element^[23]^[8].

Definition links- und rechtsneutral

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

linksneutral, falls $e \circ a = a$ für alle $a \in M$ ist,
rechtsneutral, falls $a \circ e = a$ für alle $a \in M$ ist^[24]^[8].

Lösung

Lösung

Da wir bereits gezeigt haben, dass $(ℤ / m ℤ, ⊙)$ 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 (ℤ / m ℤ, ⊙)$ existiert, für das gilt

linksneutral, also $[e]_{m} ⊙ [a]_{m} = [a]_{m}$ für alle $[a]_{m} \in (ℤ / m ℤ, ⊙)$ ,
rechtsneutral, also $[a]_{m} ⊙ [e]_{m} = [a]_{m}$ für alle $[a]_{m} \in (ℤ / m ℤ, ⊙)$ .

Wir beginnen mit linksneutral:

$[e]_{m} ⊙ [a]_{m}$

$= [e \cdot a]_{m}$ , nach Definition Multiplikation in $ℤ / m ℤ$ ,

$= [1 \cdot a]_{m}$ , da das neutrale Element der Multiplikation in $ℤ$ die Zahl $1$ ist,

( $= [1]_{m} ⊙ [a]_{m}$ )

$= [a]_{m}$

also ist $[e]_{m} = [1]_{m}$ linksneutral

Nun folgt rechtsneutral:

$[a]_{m} ⊙ [e]_{m}$

= $[a \cdot e]_{m}$ , nach Definition Multiplikation in $ℤ / m ℤ$ ,

$= [a \cdot 1]_{m}$ , da das neutrale Element der Multiplikation in $ℤ$ die Zahl $1$ ist,

( $= [a]_{m} ⊙ [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)$ ^[6]

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^[25]^[6].

Lösung

Lösung
Auch wenn die Definition des kommutativen Rings sehr lang ist, so haben wir bereits gezeigt, dass

(ℤ / m ℤ, \oplus, ⊙)

ein Ring ist und in Aufgabe 1, dass die Halbgruppe

(ℤ / m ℤ, ⊙)

ein Monoid ist, also das links- und rechtsneutrales Element

[1]_{m}

besitzt. Es bleibt also nur noch zu zeigen, dass

[a]_{m} ⊙ [b]_{m} = [b]_{m} ⊙ [a]_{m}

für alle

[a]_{m}, [b]_{m} \in (ℤ / m ℤ, ⊙)

gilt.

Wir beginnen mit

$[a]_{m} ⊙ [b]_{m}$

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

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

$= [b]_{m} ⊙ [a]_{m}$ ■^[11]

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

Literatur

↑ Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 121.
↑ Forster, O. (2015). Algorithmische Zahlentheorie (2., überarbeitete und erweiterte Auflage). Springer Spektrum. S. 45.
↑ ^3,0 ^3,1 ^3,2 ^3,3 ^3,4 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 40.
↑ Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 161.
↑ Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 6.
↑ ^6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 169.
↑ ^7,0 ^7,1 ^7,2 Seite „Halbgruppe“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 8. August 2019, 11:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Halbgruppe&oldid=191153086 (Abgerufen: 17. Dezember 2019, 10:20 UTC; Formulierung verändert)
↑ ^8,00 ^8,01 ^8,02 ^8,03 ^8,04 ^8,05 ^8,06 ^8,07 ^8,08 ^8,09 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 41.
↑ ^9,0 ^9,1 ^9,2 ^9,3 ^9,4 ^9,5 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 164.
↑ Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 168.
↑ ^11,0 ^11,1 ^11,2 ^11,3 ^11,4 ^11,5 ^11,6 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 163.
↑ ^12,0 ^12,1 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 166.
↑ Seite „Inverses Element“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 13. März 2019, 15:23 UTC. URL: https://de.wikipedia.org/w/index.php?title=Inverses_Element&oldid=186548871 (Abgerufen: 16. Dezember 2019, 14:37 UTC; Formulierung verändert)
↑ ^14,0 ^14,1 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 169.
↑ ^15,0 ^15,1 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 168f.
↑ ^16,0 ^16,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 43.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 39.
↑ Seite „Lemma von Bézout“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. Oktober 2019, 09:53 UTC. URL: https://de.wikipedia.org/w/index.php?title=Lemma_von_B%C3%A9zout&oldid=193035164 (Abgerufen: 6. Januar 2020, 13:39 UTC; Formulierung verändert)
↑ Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 47.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 153f.
↑ Seite „Monoid“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 16. Oktober 2019, 10:34 UTC. URL: https://de.wikipedia.org/w/index.php?title=Monoid&oldid=193176877 (Abgerufen: 12. Januar 2020, 12:51 UTC; Formulierung verändert)
↑ Seite „Neutrales Element“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 1. August 2019, 19:01 UTC. URL: https://de.wikipedia.org/w/index.php?title=Neutrales_Element&oldid=190957329 (Abgerufen: 12. Januar 2020, 12:55 UTC; Formulierung verändert)
↑ Seite „Ring (Algebra)“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 22. September 2019, 16:03 UTC. URL: https://de.wikipedia.org/w/index.php?title=Ring_(Algebra)&oldid=192488719 (Abgerufen: 16. Dezember 2019, 13:26 UTC; Formulierung verändert)

[1] Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 121.

[2] Forster, O. (2015). Algorithmische Zahlentheorie (2., überarbeitete und erweiterte Auflage). Springer Spektrum. S. 45.

[:7-3] 3,0 ^3,1 ^3,2 ^3,3 ^3,4 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 40.

[4] Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 161.

[5] Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 6.

[:224-6] 6,0 ^6,1 ^6,2 ^6,3 ^6,4 ^6,5 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 169.

[:44-7] 7,0 ^7,1 ^7,2 Seite „Halbgruppe“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 8. August 2019, 11:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Halbgruppe&oldid=191153086 (Abgerufen: 17. Dezember 2019, 10:20 UTC; Formulierung verändert)

[:15-8] 8,00 ^8,01 ^8,02 ^8,03 ^8,04 ^8,05 ^8,06 ^8,07 ^8,08 ^8,09 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 41.

[:223-9] 9,0 ^9,1 ^9,2 ^9,3 ^9,4 ^9,5 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 164.

[10] Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 168.

[:3-11] 11,0 ^11,1 ^11,2 ^11,3 ^11,4 ^11,5 ^11,6 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 163.

[:5-12] 12,0 ^12,1 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 166.

[13] Seite „Inverses Element“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 13. März 2019, 15:23 UTC. URL: https://de.wikipedia.org/w/index.php?title=Inverses_Element&oldid=186548871 (Abgerufen: 16. Dezember 2019, 14:37 UTC; Formulierung verändert)

[:1-14] 14,0 ^14,1 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 169.

[:4-15] 15,0 ^15,1 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 168f.

[:0-16] 16,0 ^16,1 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 43.

[:322-17] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.

[:72-18] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.

[19] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 39.

[:2-20] Seite „Lemma von Bézout“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. Oktober 2019, 09:53 UTC. URL: https://de.wikipedia.org/w/index.php?title=Lemma_von_B%C3%A9zout&oldid=193035164 (Abgerufen: 6. Januar 2020, 13:39 UTC; Formulierung verändert)

[:34-21] Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 47.

[22] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 153f.

[23] Seite „Monoid“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 16. Oktober 2019, 10:34 UTC. URL: https://de.wikipedia.org/w/index.php?title=Monoid&oldid=193176877 (Abgerufen: 12. Januar 2020, 12:51 UTC; Formulierung verändert)

[24] Seite „Neutrales Element“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 1. August 2019, 19:01 UTC. URL: https://de.wikipedia.org/w/index.php?title=Neutrales_Element&oldid=190957329 (Abgerufen: 12. Januar 2020, 12:55 UTC; Formulierung verändert)

[25] Seite „Ring (Algebra)“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 22. September 2019, 16:03 UTC. URL: https://de.wikipedia.org/w/index.php?title=Ring_(Algebra)&oldid=192488719 (Abgerufen: 16. Dezember 2019, 13:26 UTC; Formulierung verändert)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Kryptologie/Restklassenring: Unterschied zwischen den Versionen

Aktuelle Version vom 22. April 2020, 18:44 Uhr

Inhaltsverzeichnis

Einleitung

Restklassenring

Beweis Restklassenring

1. $(ℤ / m ℤ, \oplus)$ ist eine kommutative Gruppe

1.1 $(ℤ / m ℤ, \oplus)$ ist eine Gruppe

1.1.1 Für $(ℤ / m ℤ, \oplus)$ gilt das Assoziativgesetz

1.1.2 $(ℤ / m ℤ, \oplus)$ besitzt ein neutrales Element

1.1.3 $(ℤ / m ℤ, \oplus)$ besitzt ein inverses Element

1.2 Für $(ℤ / m ℤ, \oplus)$ gilt das Kommutativgesetz

2. $(ℤ / m ℤ, ⊙)$ ist eine Halbgruppe

2.1 Assoziativität von $(ℤ / m ℤ, ⊙)$

3. Distributivgesetze

Multiplikative Inverse im Restklassenring $(ℤ / m ℤ, \oplus, ⊙)$

Satz Multiplikative Inverse in $(ℤ / m ℤ, \oplus, ⊙)$

Beweis Multiplikative Inverse in $(ℤ / m ℤ, \oplus, ⊙)$

Lernaufgabe

Aufgabe 1

Aufgabe 2

Lernempfehlung

Literatur

Navigationsmenü

Kryptologie/Restklassenring: Unterschied zwischen den Versionen

Aktuelle Version vom 22. April 2020, 18:44 Uhr

Einleitung

Restklassenring

Beweis Restklassenring

1. (ℤ/mℤ,⊕) ist eine kommutative Gruppe

1.1 (ℤ/mℤ,⊕) ist eine Gruppe

1.1.1 Für (ℤ/mℤ,⊕) gilt das Assoziativgesetz

1.1.2 (ℤ/mℤ,⊕) besitzt ein neutrales Element

1.1.3 (ℤ/mℤ,⊕) besitzt ein inverses Element

1.2 Für (ℤ/mℤ,⊕) gilt das Kommutativgesetz

2. (ℤ/mℤ,⊙) ist eine Halbgruppe

2.1 Assoziativität von (ℤ/mℤ,⊙)

3. Distributivgesetze

Multiplikative Inverse im Restklassenring (ℤ/mℤ,⊕,⊙)

Satz Multiplikative Inverse in (ℤ/mℤ,⊕,⊙)

Beweis Multiplikative Inverse in (ℤ/mℤ,⊕,⊙)

Lernaufgabe

Aufgabe 1

Aufgabe 2

Lernempfehlung

Literatur

Navigationsmenü

Suche

1. $(ℤ / m ℤ, \oplus)$ ist eine kommutative Gruppe

1.1 $(ℤ / m ℤ, \oplus)$ ist eine Gruppe

1.1.1 Für $(ℤ / m ℤ, \oplus)$ gilt das Assoziativgesetz

1.1.2 $(ℤ / m ℤ, \oplus)$ besitzt ein neutrales Element

1.1.3 $(ℤ / m ℤ, \oplus)$ besitzt ein inverses Element

1.2 Für $(ℤ / m ℤ, \oplus)$ gilt das Kommutativgesetz

2. $(ℤ / m ℤ, ⊙)$ ist eine Halbgruppe

2.1 Assoziativität von $(ℤ / m ℤ, ⊙)$

Multiplikative Inverse im Restklassenring $(ℤ / m ℤ, \oplus, ⊙)$

Satz Multiplikative Inverse in $(ℤ / m ℤ, \oplus, ⊙)$

Beweis Multiplikative Inverse in $(ℤ / m ℤ, \oplus, ⊙)$