2.6 – Größter gemeinsamer Teiler, Euklidischer Algorithmus

 

2.6.1 Definition und Verwendung

Seien a,b \in \mathbb{Z}\backslash \left\{ 0 \right\}. Eine Zahl d \in \mathbb{N} heißt größter gemeinsamer Teiler von a und b, abgekürzt ggT\left( {a,b} \right), wenn folgende Eigenschaften gelten:

  1. d teilt a und d teilt b, also d|a,\:\:d|b
  2. Falls für c \in \mathbb{Z} gilt: c|a und c|b, dann folgt daraus c|d.

Gilt für zwei Zahlen ggT\left( {a,b} \right) = 1, dann nennt man a und b teilerfremd.

Sei n \in \mathbb{N}, sei \left( {\mathbb{Z}/n\mathbb{Z},+, \cdot } \right) ein Restklassenring, sei \bar a \in \mathbb{Z}/n\mathbb{Z} eine Restklasse mit einem Repräsentanten a \in \mathbb{Z}. Es existiert genau dann ein multiplikatives Inverses zu a, wenn a und n teilerfremd sind. Das bedeutet, dass der Schlüssel bei der oben besprochenen Multiplikationschiffre teilerfremd zu der Anzahl der möglichen Buchstaben sein muss, damit der Algorithmus zulässig ist.
3 ist teilerfremd zu 26, aber 2 und 8 sind nicht teilerfremd zu 26.

2.6.2 Einfache Bestimmung des ggT

Einfachste Version: Es wird eine Primfaktorzerlegung durchgeführt. Die gemeinsamen Primfaktoren sind multipliziert der größte gemeinsame Teiler. Dieses System funktioniert bei modernen Kryptosystemen allerdings nicht, da die Zahlen zu groß sind, um die Primfaktoren schnell finden zu können. Stattdessen verwenden wir den folgenden Algorithmus.

2.6.3 Euklidischer Algorithmus

Der Euklidische Algorithmus dient zur effizienten Berechnung des größten gemeinsamen Teilers ohne Primfaktorzerlegung. Wenn wir den ggT von a und b suchen, gehen wir wie folgt vor:

b = {q_1}a+{r_1},\quad 0 \leq {r_1} < a

a = {q_2}{r_1}+{r_2},\quad 0 \leq {r_2} < {r_1}

{r_1} = {q_3}{r_2}+{r_3},\quad 0 \leq {r_3} < {r_2}

Die Reste werden immer kleiner. Der Algorithmus endet, wenn {r_{n+1}} = 0 ist. Der größte gemeinsame Teiler ist der letzte von Null verschiedene Rest. Dies gilt, weil

{r_n} = ggT\left( {0,{r_n}} \right) = ggT\left( {{r_{n-1}},{r_n}} \right) = \ldots = ggT\left( {a,b} \right)

Beispiel:

ggT\left( {160,13} \right)

160 = 12 \cdot 13+4

13 = 3 \cdot 4+\boxed1

4 = 4 \cdot 1+0

ggT\left( {160,13} \right) = 1

Ein weiteres Beispiel:

ggT\left( {13,8} \right)

13 = 1 \cdot 8+5

8 = 1 \cdot 5+3

5 = 1 \cdot 3+2

3 = 1 \cdot 2+\boxed1

2 = 2 \cdot 1+0

Man kann beweisen, dass die Anzahl der Schritte maximal wird, wenn beide Zahlen Fibonaccizahlen sind.

2.6.4 Erweiterter Euklidischer Algorithmus

Seien a,b \in \mathbb{Z} und sei d = ggT\left( {a,b} \right). Dann existieren zwei ganze Zahlen s,t \in \mathbb{Z}, so dass

ggT\left( {a,b} \right) = d = s \cdot a+t \cdot b

Beweisskizze:

{r_1} = b-{q_1} \cdot a

{r_2} = a-{q_2} \cdot {r_1}

{r_3} = {r_1}-{q_3} \cdot {r_2}

\vdots

{r_n} = {r_{n-2}}-{q_n} \cdot {r_{n-1}}

{r_n} = ggT\left( {a,b} \right) = s \cdot a+t \cdot b

Beispiel:

ggT\left( {13,8} \right) = 1

1 = 3-1 \cdot 2\quad |\:2 = 5-1 \cdot 3

1 = 3-1 \cdot \left( {5-1 \cdot 3} \right) = 2 \cdot 3-1 \cdot 5\quad |3 = 8-1 \cdot 5

1 = 2 \cdot \left( {8-1 \cdot 5} \right)-1 \cdot 5 = 2 \cdot 8-3 \cdot 5\quad |5 = 13-1 \cdot 8

1 = 2 \cdot 8-3 \cdot \left( {13-1 \cdot 8} \right) = 5 \cdot 8-3 \cdot 13

\quad \Rightarrow \quad s = -3,\quad t = 5

Wir rechnen nun mit Modulo:

1\bmod 13 = \left( {5 \cdot 8+\left( {-3} \right) \cdot 13} \right)\bmod 13 = 5 \cdot 8+0

Das multiplikative Inverse ist also 5. Wir haben nun einen Weg, um das Inverse für die Modulorechnung zu bestimmen.

Beispiel:

Multiplikationschiffre mit k = 3.

p = BOB \overset{\wedge}{=}\left( {1,14,1} \right)

{c_i} = \left( {{p_i} \cdot {k_i}} \right)\bmod 26

c = \left( {3,16,3} \right) \overset{\wedge}{=}DQD

Aufgabe: Bestimme die Entschlüsselungsfunktion!

1. Schritt: Euklidischer Algorithmus, berechne ggT\left( {26,3} \right):

26 = 8 \cdot 3+2

3 = 1 \cdot 2+\boxed1

2 = 2 \cdot 1+0

Da der größte gemeinsame Teiler 1 ist, ist 3 ein zulässiger Faktor für die Verschlüsselung.

2. Schritt: Erweiterter Euklidischer Algorithmus, berechne s,t:

1 = 3-1 \cdot 2\quad |2 = 26-8 \cdot 3

1 = 3-1 \cdot \left( {26-8 \cdot 3} \right) = 9 \cdot 3-1 \cdot 26

3. Schritt: gesamte Gleichung modulo 26 nehmen:

1 \equiv 9 \cdot 3+0

Entschlüsselung: {p_i} = \left( {9 \cdot {c_i}} \right)\bmod 26

Probe:

c = \left( {3,16,3} \right)

{k^{-1}} = 9 = q

p = \left( {1,14,1} \right) \overset{\wedge}{=}BOB