Kryptologie/Größte gemeinsame Teiler

Einleitung

Für viele Beweise in diesem Kurs benötigen wir die Definition des größten gemeinsamen Teilers oder dessen Lemmata. Das sogenannte Lemma von Bézout brauchen wir beispielsweise für den erweiterten euklidischen Algorithmus^[1] oder das Lemma von Euklid um den Fundamentalsatz der Zahlentheorie zu zeigen^[2]. Beides benötigen wir für das RSA-Kryptosystem (Schlüsselerzeugung^[3] und Korrektheit des Verfahrens^[4]). Aber auch beim Caesar-Kryptosystem benötigen wir den größten gemeinsame Teiler^[5].

Größter gemeinsamer Teiler

Definition Größter gemeinsamer Teiler

Seien $a, b \in ℤ$ , wobei mindestens eine der beiden Zahlen ungleich Null ist. 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$ ^[6].

Beispiel Größter gemeinsamer Teiler

Sei $a = - 14$ und $b = 32$ .

$a = - 14$ hat die folgenden Teiler: $- 14, - 7, - 2, - 1, 1, 2, 7$ und $14$ .

$b = 32$ hat die Teiler: $- 32, - 16, - 8, - 4, - 2, - 1, 1, 2, 4, 8, 16$ und $32$ .

$a$ und $b$ haben also die gemeinsamen Teiler $- 2, - 1, 1$ und $2$ .

Der größte gemeinsame Teiler ist $2$ und somit $g g T (- 14, 32) = 2$ .

Bemerkung: Bei größeren Zahlen kann das Bestimmen des größten gemeinsamen Teilers auf diese Art sehr lange dauern. Eine effizientere Methode ist der (erweiterte) euklidische Algorithmus^[7]. Für diese Methoden müssen jedoch die Eigenschaften des $g g T$ näher betrachten^[1].

Eigenschaften

Lemma 1

Seien $a, b \in ℤ$ , wobei nicht $a = b = 0$ . Es gilt $g g T (| a |, | b |) = g g T (a, b)$ ^[8].

Beweis Lemma 1

Größte gemeinsame Teiler und Lemma der Teilbarkeit
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$ ^[6].
Lemma der Teilbarkeit: $(1)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ b \Leftrightarrow a ∣ (- b)$ ^[9]

Voraussetzung

$d = g g T (| a |, | b |)$ und $a, b \in ℤ$ .

Zu zeigen

$g g T (| a |, | b |) = g g T (a, b)$

bzw. wegen Definition des absoluten Betrags $∣ a ∣$ als $| a | = a$ oder $| a | = - a$ ^[10]

$g g T (a, b) = g g T (- a, b) = g g T (a, - b) = g g T (- a, - b)$ .

Beweis

Betrachten wir $d = g g T (a, b)$ .

Nach Definition des größten gemeinsamen Teilers gilt $d ∣ a$ und $d ∣ b$ .

Wir wissen nach $(1)$ des Lemmas der Teilbarkeit, dass dann auch gilt

$d ∣ (- a)$ und $d ∣ (- b)$ .

Sei nun $t \in ℤ$ ein beliebiger gemeinsamer Teiler von $- a$ und $b$ oder von $a$ und $- b$ oder von $- a$ und $- b$ .

Nach $(1)$ des Satzes der Teilbarkeit gilt dann $t ∣ a$ und $t ∣ b$ , wobei in jedem Fall $t \leq d$ , da $d = g g T (a, b)$ ist.

Somit gilt $g g T (a, b) = g g T (- a, b) = g g T (a, - b) = g g T (- a, - b)$ ■^[11]

Lemma 2

Seien $a, b, k, r \in ℤ$ und $a = k \cdot b + r$ , dann folgt: $g g T (a, b) = g g T (b, r)$ ^[12].

Beweis Lemma 2

Größte gemeinsame Teiler und Lemma der Teilbarkeit
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$ ^[13].
Lemma der Teilbarkeit: $(3)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ b$ und $a ∣ c \Rightarrow a ∣ (b s + c t)$ für beliebige $s, t \in ℤ$ ^[14].

Voraussetzung

$a, b, k, r \in ℤ$ und $a = k \cdot b + r$ .

Zu zeigen

$g g T (a, b) = g g T (b, r)$

Beweis

Wenn $g g T (a, b) = d$ , dann gilt nach Definition des größten gemeinsamen Teilers $d ∣ a$ und $d ∣ b$ .

Aus $d ∣ a$ und $d ∣ b$ folgt wiederum nach $(3)$ des Lemmas der Teilbarkeit, dass $d ∣ (a - b)$ bzw. $d ∣ (a - k \cdot b)$ .

$d ∣ (a - k \cdot b)$ lässt sich nach der Voraussetzung $a = k \cdot b + r$ umschreiben in $d ∣ r$ und somit ist $d$ also ein Teiler von $r$ .

Wir konstruieren nun einen beliebigen gemeinsamen Teiler $c$ mit $c ∣ b$ und $c ∣ r$ und somit gilt auch $c ∣ (k \cdot b + r)$ .

Da $a = k \cdot b + r$ , gilt für den Teiler $c$ also außerdem $c ∣ a$ .

$c$ ist also auch ein gemeinsamer Teiler von $a$ und $b$ . Jedoch ist $g g T (a, b) = d$ und es muss daher $c \leq d$ sein.

Wir haben also gezeigt, dass ein beliebiger gemeinsamer Teiler $c$ von $b$ und $r$ auch ein gemeinsamer Teiler von $a$ und $b$ ist, wobei $c \leq d$ und zusätzlich $d ∣ r$ . Somit ist der größte gemeinsame Teiler von $b$ und $r$ ebenfalls $d$ . Formal gilt also: $d = g g T (b, r)$ ■^[1]

Lemma 3 (Lemma von Bézout)

Bemerkung: Da wir für die Schlüsselerzeugung des RSA-Algorithmus' teilerfremde ganze Zahlen mit dem erweiterten euklidischen Algorithmus untersuchen, betrachten wir insbesondere teilerfremde ganze Zahlen $a$ und $b$ . Für diese gilt folglich: $g g T (a, b) = 1 = s \cdot a + t \cdot b$ ^[15] für geeignete $s, t \in ℤ$ .

Das Lemma von Bézout besagt, dass sich der größte gemeinsame Teiler zweier ganzer Zahlen $a$ und $b$ als Linearkombination von $a$ und $b$ mit ganzzahligen Koeffizienten darstellen lässt^[15]. Formal schreiben wir:

Für alle $a, b \in ℤ$ existieren $s, t \in ℤ$ , sodass gilt: $g g T (a, b) = s \cdot a + t \cdot b$ ^[16]^[17].

Beweis Lemma 3 (Lemma von Bézout)

Voraussetzung

Seien $a, b \in ℤ$

Zu zeigen

Es existieren $s, t \in ℤ$ , sodass $g g T (a, b) = s \cdot a + t \cdot b$ gilt

Beweis

Lemma der Teilbarkeit, Division mit Rest und Umformung
Lemma der Teilbarkeit: $(3)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ b$ und $a ∣ c \Rightarrow a ∣ (b s + c t)$ für beliebige $s, t \in ℤ$ ^[14].
Division mit Rest
Seien $a, b \in ℤ$ mit $b \neq 0$ eindeutig bestimmte Zahlen $k \in ℤ$ und $r \in ℕ$ gibt, für die gilt: $a = k \cdot b + r, 0 \leq r < \| b \|$ ^[18]^[19].
Umformungen
$a = k \cdot d + r$ $\Leftrightarrow a = k \cdot (s \cdot a + t \cdot b) + r$ , da $d = s \cdot a + t \cdot b$ $\Leftrightarrow a - k \cdot (s \cdot a + t \cdot b) = r$ $\Leftrightarrow a - k \cdot s \cdot a - k \cdot t \cdot b = r$ $\Leftrightarrow a \cdot (1 - k \cdot s) - k \cdot t \cdot b = r$ $\Leftrightarrow a \cdot (1 - k \cdot s) + (- k \cdot t) \cdot b = r$

Wir nehmen an, dass es unter allen Zahlen $x = s \cdot a + t \cdot b$ mit $s, t \in ℤ$ sicher solche gibt, die positiv und ungleich Null sind.

Sei $d = s \cdot a + t \cdot b$ die kleinste Zahl unter diesen.

Da $ggT (a, b)$ sowohl $a$ als auch $b$ teilt, teilt $ggT (a, b)$ nach $(3)$ des Lemmas der Teilbarkeit auch $d$ .

Wir zeigen nun, dass $d$ auch ein Teiler von $a$ und $b$ ist.

Die Division mit Rest liefert uns eine Darstellung von $a$ in der Form $a = k \cdot d + r$ , wobei $0 \leq r < d$ .

Wir setzen nun $d = s \cdot a + t \cdot b$ in die Darstellung von $a$ ein und lösen die Gleichung nach $r$ auf.

Wir erhalten nach mehrmaligem Umformen $r = (1 - k \cdot s) \cdot a + (- k \cdot t) \cdot b$ .

Da $d$ die kleinste positive Zahl ist, welche die oben genannte Eigenschaft erfüllt, muss $r = 0$ sein.

Es gilt $a = k \cdot d$ und $d$ ist somit nach der Definition der Teilbarkeit ein Teiler von $a$ .

Entsprechend gilt auch, dass $d$ ein Teiler von $b$ ist und es gilt $d \leq ggT (a, b)$ .

Wir hatten bereits thematisiert, dass $ggT (a, b)$ ein Teiler von $d$ ist und folgern nun $d = ggT (a, b)$ ■^[15]^[17]

Folgerung aus dem Lemma von Bézout

Seien $a, b \in ℤ$ , , wobei mindestens einer der beiden Zahlen ungleich Null, dann besteht $V = {a x + b y | x, y \in ℤ}$ genau aus den Vielfachen von $d = g g T (a, b)$ ^[20].

Beweis Folgerung aus dem Lemma von Bézout

Größte gemeinsame Teiler, Lemma der Teilbarkeit und Linearkombination
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$ ^[6].
Lemma der Teilbarkeit: $(3)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ b$ und $a ∣ c \Rightarrow a ∣ (b s + c t)$ für beliebige $s, t \in ℤ$ ^[21].

Voraussetzung

Seien $a, b \in ℤ$ , , wobei mindestens einer der beiden Zahlen ungleich Null und $V = {a x + b y | x, y \in ℤ}$ .

Zu zeigen

$V = {a x + b y | x, y \in ℤ}$ besteht genau aus den Vielfachen von $d = g g T (a, b)$ .

Beweis

Nach Definition des größten gemeinsamen Teilers gilt $d ∣ a$ und $d ∣ b$ .

Es gilt dann $d ∣ (a x + b y)$ nach $(3)$ des Lemmas der Teilbarkeit für beliebige $x, y \in ℤ$ .

Wir wissen nach dem Lemma von Bézout, dass $d = g g T (a, b) = a x_{1} + b y_{1}$ .

Wir können Vielfache von $d$ also schreiben als $m d = m (a x_{1} + b y_{1}) = a (m x_{1}) + b (m y_{1})$ mit $m \in ℤ$ .

Somit ist aber auch jedes Vielfache von $d$ als Linearkombination von $a$ und $b$ darstellbar und Element der Menge $V = {a x + b y | x, y \in ℤ}$ ■^[20]

Lemma 4

Seien $a, b \in ℤ$ , wobei mindestens eine der beiden Zahlen ungleich Null.

$a$ und $b$ sind genau dann teilerfremd zueinander, wenn $s, t \in ℤ$ existieren, sodass gilt:

$1 = a s + b t$ ^[20].

Beweis Lemma 4

Hinrichtung

Wir zeigen zunächst, dass aus der Teilerfremdheit von $a$ und $b$ die Aussage $1 = a s + b t$ mit geeigneten $s, t \in ℤ$ folgt.

Voraussetzung

Teilerfremdheit, Lemma von Bézout, Größte gemeinsame Teiler und Lemma der Teilbarkeit
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $g g T (a, b) = 1$ ^[22]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[23]^[20].
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$ ^[15]^[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$ ^[6].
Lemma der Teilbarkeit: $(3)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ b$ und $a ∣ c \Rightarrow a ∣ (b s + c t)$ für beliebige $s, t \in ℤ$ ^[14].
Lemma der Teilbarkeit: $(2)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ 1 \Leftrightarrow a = \pm 1$ ^[14].

Seien $a, b \in ℤ$ , wobei mindestens einer der beiden Zahlen ungleich Null und $a, b$ teilerfremd zueinander.

Zu zeigen

Es existieren $s, t \in ℤ$ , sodass gilt $1 = a s + b t$ .

Beweis

Da nach Voraussetzung die Zahlen $a$ und $b$ teilerfremd sind, folgt aus der Definition von teilerfremd, dass gilt:

$g g T (a, b) = 1$ .

Benutzt man nun das Lemma von Bézout folgt:

Es existieren $s, t \in ℤ$ mit $g g T (a, b) = 1 = a s + b t$ .

Rückrichtung

Nun zeigen wir die umgekehrte Richtung.

Voraussetzung

Sei $1 = a s + b t$ mit $s, t \in ℤ$ .

Zu zeigen

$a, b$ sind teilerfremd zueinander mit $a, b \in ℤ$ , wobei mindestens eine der beiden Zahlen ungleich Null.

Beweis

Sei nach Voraussetzung $1 = a s + b t$ mit $s, t \in ℤ$ und $d = g g T (a, b)$ .

Da nach Definition des größten gemeinsamen Teilers $d ∣ a$ und $d ∣ b$ gilt, folgt nach $(3)$ des Lemmas der Teilbarkeit

$d ∣ (a s + b t)$ .

Nach Voraussetzung ist dies gerade

$d ∣ 1$ .

Da $d$ positiv, folgt aus $(2)$ des Lemmas der Teilbarkeit

$d = 1$ .

Nach der Definition teilerfremd folgt

$a, b$ sind teilerfremd zueinander, wobei mindestens einer der beiden Zahlen ungleich Null^[20].

Folgerung aus Lemma 4

Gilt $a ∣ c$ und $b ∣ c$ mit $g g T (a, b) = 1$ , dann folgt $a b ∣ c$ ^[20].

Beweis der Folgerung

Teilbarkeit und Lemma 4 des $g g T$
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $k$ gibt, für die $a \cdot k = b$ ist. Wir schreiben $a ∣ b$ ^[24]^[25].
Lemma 4 des $g g T$
Seien $a, b \in ℤ$ , wobei mindestens einer der beiden Zahlen ungleich Null. $a$ und $b$ sind genau dann teilerfremd zueinander, wenn $s, t \in ℤ$ existieren, sodass gilt: $1 = a s + b t$ ^[22].

Voraussetzung

$a ∣ c$ und $b ∣ c$ mit $g g T (a, b) = 1$ .

Zu zeigen

$a b ∣ c$ .

Beweis

Aus der Voraussetzung folgern wir nach der Definition der Teilbarkeit

$a k_{1} = c$ und $b k_{2} = c$ mit $k_{1}, k_{2} \in ℤ$ geeignet

bzw. zusammengefasst

$c = a k_{1} = b k_{2}$ .

Wegen $g g T (a, b) = 1$ gilt nach Lemma 4 des $g g T$

$1 = a s + b t$ mit $s, t \in ℤ$

$\Leftrightarrow c = c a s + c b t$ , durch Multiplikation mit $c$ .

Nun können wir $a k_{1} = c$ bzw. $b k_{2} = c$ einsetzen

$\Leftrightarrow c = a b k_{2} s + b a k_{1} t$

$\Leftrightarrow c = a b (k_{2} s + k_{1} t)$

Dies ist nach Definition der Teilbarkeit

$\Leftrightarrow a b ∣ c$ ■^[26]

Lemma 5 (Lemma von Euklid)

Seien $n \in ℕ$ und $a, b \in ℤ$ mit $n ∣ a b$ und ist nun $n$ teilerfremd zu einem der Faktoren, so teilt es den anderen^[27]^[26].

Beweis Lemma 5

Den Beweis können Sie in der Lernaufgabe eigenständig führen.

Lernaufgabe

Lemma von Euklid, Teilerfremdheit, Lemma 4 des $g g T$ und Teilbarkeit
Lemma von Euklid
Seien $n \in ℕ$ und $a, b \in ℤ$ mit $n ∣ a b$ und ist nun $n$ teilerfremd zu einem der Faktoren, so teilt es den anderen^[27]^[26].
Teilerfremdheit
Zwei ganze Zahlen $a$ und $b$ , wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $g g T (a, b) = 1$ ^[22]. Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind^[23]^[22].
Lemma 4 des $g g T$
Seien $a, b \in ℤ$ , wobei mindestens einer der beiden Zahlen ungleich Null. $a$ und $b$ sind genau dann teilerfremd zueinander, wenn $s, t \in ℤ$ existieren, sodass gilt: $1 = a s + b t$ ^[22].
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $k$ gibt, für die $a \cdot k = b$ ist. Wir schreiben $a ∣ b$ ^[24]^[25].

Aufgabe

Beweisen Sie das Lemma von Euklid. Nehmen Sie hierfür an, dass $a$ teilerfremd zu $n$ und multiplizieren Sie die Gleichung aus Lemma 4 des $g g T$ mit $b$ .

Lösung

Voraussetzung

Seien $n \in ℕ$ und $a, b \in ℤ$ , $n ∣ a b$ und $n$ teilerfremd zu einem der Faktoren $a b$

Zu zeigen

$n$ teilt den anderen Faktor

Beweis

Wir nehmen an, dass $a$ teilerfremd zu $n$ . Folglich gilt $g g T (a, n) = 1$ .

Nach Lemma 4 des $g g T$ gilt

$1 = a x + n y$ mit $x, y \in ℤ$

$\Leftrightarrow b = b (a x + n y) = b a x + b n y$ , durch Multiplikation mit $b$

Nun gilt nach der Definition der Teilbarkeit und Voraussetzung $n ∣ b a$ und zusätzlich $n ∣ b n$ .

Somit gilt auch $n ∣ (b a x + b n y)$ .

Wir haben jedoch gezeigt, dass $b = b a x + b n y$ gilt und können folgern

$n ∣ b$ ■^[28]

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4.1: Teilbarkeit und Teilerfremdheit	4.2: Größte gemeinsame Teiler	4.3: Kongruenzen

Literatur

↑ ^1,0 ^1,1 ^1,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 32.
↑ Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 66.
↑ Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 122f.
↑ Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). 123.
↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 43.
↑ ^6,0 ^6,1 ^6,2 ^6,3 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 31.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 30.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 29.
↑ Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 34.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 476.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 32.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
↑ ^14,0 ^14,1 ^14,2 ^14,3 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.
↑ ^15,0 ^15,1 ^15,2 ^15,3 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)
↑ Bézout, E. (1779). Théorie générale des équations algébriques. Paris, Impr. de P.-D. Pierres.
↑ ^17,0 ^17,1 ^17,2 Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 47.
↑ Seite „Division mit Rest“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. Januar 2020, 18:50 UTC. URL: https://de.wikipedia.org/w/index.php?title=Division_mit_Rest&oldid=196144598 (Abgerufen: 2. Februar 2020, 14:22 UTC; Formulierung verändert)
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 19.
↑ ^20,0 ^20,1 ^20,2 ^20,3 ^20,4 ^20,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.
↑ ^22,0 ^22,1 ^22,2 ^22,3 ^22,4 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
↑ ^23,0 ^23,1 Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert; Formulierung verändert)
↑ ^24,0 ^24,1 Seite „Teilbarkeit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 15:44 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilbarkeit&oldid=194364839 (Abgerufen: 12. Dezember 2019, 14:43 UTC; Formulierung verändert)
↑ ^25,0 ^25,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.
↑ ^26,0 ^26,1 ^26,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 27.
↑ ^27,0 ^27,1 Seite „Lemma von Euklid“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. Juli 2018, 11:20 UTC. URL: https://de.wikipedia.org/w/index.php?title=Lemma_von_Euklid&oldid=179437094 (Abgerufen: 7. Januar 2020, 11:06 UTC; Formulierung verändert)
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 27f.

[:10-1] 1,0 ^1,1 ^1,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 32.

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

[3] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 122f.

[4] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). 123.

[5] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 43.

[:7-6] 6,0 ^6,1 ^6,2 ^6,3 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.

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

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

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

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

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

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

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

[:06-14] 14,0 ^14,1 ^14,2 ^14,3 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.

[:2-15] 15,0 ^15,1 ^15,2 ^15,3 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)

[16] Bézout, E. (1779). Théorie générale des équations algébriques. Paris, Impr. de P.-D. Pierres.

[:3-17] 17,0 ^17,1 ^17,2 Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 47.

[18] Seite „Division mit Rest“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. Januar 2020, 18:50 UTC. URL: https://de.wikipedia.org/w/index.php?title=Division_mit_Rest&oldid=196144598 (Abgerufen: 2. Februar 2020, 14:22 UTC; Formulierung verändert)

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

[:9-20] 20,0 ^20,1 ^20,2 ^20,3 ^20,4 ^20,5 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.

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

[:922-22] 22,0 ^22,1 ^22,2 ^22,3 ^22,4 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.

[:55-23] 23,0 ^23,1 Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert; Formulierung verändert)

[:12-24] 24,0 ^24,1 Seite „Teilbarkeit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 15:44 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilbarkeit&oldid=194364839 (Abgerufen: 12. Dezember 2019, 14:43 UTC; Formulierung verändert)

[:222-25] 25,0 ^25,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.

[:8-26] 26,0 ^26,1 ^26,2 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 27.

[:4-27] 27,0 ^27,1 Seite „Lemma von Euklid“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. Juli 2018, 11:20 UTC. URL: https://de.wikipedia.org/w/index.php?title=Lemma_von_Euklid&oldid=179437094 (Abgerufen: 7. Januar 2020, 11:06 UTC; Formulierung verändert)

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

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

[26]

[27]

[28]

Kryptologie/Größte gemeinsame Teiler

Inhaltsverzeichnis

Einleitung

Größter gemeinsamer Teiler

Definition Größter gemeinsamer Teiler

Beispiel Größter gemeinsamer Teiler

Eigenschaften

Lemma 1

Beweis Lemma 1

Lemma 2

Beweis Lemma 2

Lemma 3 (Lemma von Bézout)

Beweis Lemma 3 (Lemma von Bézout)

Folgerung aus dem Lemma von Bézout

Beweis Folgerung aus dem Lemma von Bézout

Lemma 4

Beweis Lemma 4

Folgerung aus Lemma 4

Beweis der Folgerung

Lemma 5 (Lemma von Euklid)

Beweis Lemma 5

Lernaufgabe

Aufgabe

Lernempfehlung

Literatur

Navigationsmenü

Kryptologie/Größte gemeinsame Teiler

Einleitung

Größter gemeinsamer Teiler

Definition Größter gemeinsamer Teiler

Beispiel Größter gemeinsamer Teiler

Eigenschaften

Lemma 1

Beweis Lemma 1

Lemma 2

Beweis Lemma 2

Lemma 3 (Lemma von Bézout)

Beweis Lemma 3 (Lemma von Bézout)

Folgerung aus dem Lemma von Bézout

Beweis Folgerung aus dem Lemma von Bézout

Lemma 4

Beweis Lemma 4

Folgerung aus Lemma 4

Beweis der Folgerung

Lemma 5 (Lemma von Euklid)

Beweis Lemma 5

Lernaufgabe

Aufgabe

Lernempfehlung

Literatur

Navigationsmenü

Suche