Kapitel 1

Interim

↓17.11.04

Da ich keine Infos über Titel und Nummerierungen anderer Kapitel dieser Vorlesung habe, nenne ich dies einfach mal “Kapitel 1”.

1.1 Einige formale Definitionen

Wir rekapitulieren zunächst einige der in den letzten Wochen vorgestellten Begriffe und formalisieren sie:

Definition 1.1: (Gruppe)

Eine Menge G mit einer binären Operation ∘: G × G ↦ G (also a ∘ b ∈ G ∀a, b ∈ G) heißt Gruppe, wenn

a) die Gruppenoperation ∘ assoziativ ist: (a∘b)∘c = a∘(b∘c) ∀a, b, c ∈ G,

b) es ein “neutrales Element” e ∈ G gibt mit e∘a = a∘e = a ∀ a ∈ G,

c) es zu jedem a ∈ G ein “inverses Element” a^{−1} ∈ G gibt mit a^{−1} ∘ a = a ∘ a^{−1} = e.

Die Verknüpfung ∘ heißt kommutativ, wenn a ∘ b = b ∘ a ∀a, b ∈ G gilt. Ist ∘ kommutativ, so nennt man die Gruppe kommutativ oder auch abelsch.

Bemerkung 1.2: Zu jedem Element einer Gruppe ist die Inverse eindeutig. Angenommen, es gäbe 2 Elemente b_{1} und b_{2} mit

b_{1} ∘ a = e, b_{2} ∘ a = e, e ∘ b_{1} = e, e ∘ b_{2} = e.

“Multiplizieren” wir b_{1} ∘ a = e von rechts mit b_{2}, folgt

\underbrace{(b_{1} ∘ a) ∘ b_{2}}_{= b_{1}∘\underbrace{(a ∘ b_{2})}_{= e}} = e ∘ b_{2} ⇒ b_{1} ∘ e = e ∘ b_{2} ⇒ b_{1} = b_{2}.

2 KAPITEL 1. INTERIM

Beispiel 1.3: In den folgenden Beispielen seien + und · die übliche Addition bzw. Multiplikation in ℤ, ℚ, ℝ:

1) (ℤ, +) ist eine abelsche Gruppe: das neutrale Element ist 0, die additive Inverse a^{−1} wird als −a geschrieben.

2) (ℤ, ·) mit der üblichen Multiplikation · ist keine Gruppe: der einzige Kandidat für das neutrale Element wäre 1, aber es gibt z.B. zu a = 2 kein inverses Element (der einzige Kandidat a^{−1} = 1/2 liegt nicht in ℤ).

3) (ℚ, +) ist eine abelsche Gruppe, das neutrale Element ist 0, die additive Inverse a^{−1} wird als −a geschrieben.

4) (ℚ\{0}, ·) ist eine abelsche Gruppe, das neutrale Element ist 1, die multiplikative Inverse a^{−1} wird als 1/a geschrieben.

5) Für jedes n ∈ ℕ ist die Menge ℤ_{n} = {0, 1, …, n − 1} mit der Addition a ∘ b = (a + b) mod n eine abelsche Gruppe, das neutrale Element ist 0, die additive Inverse zu a ∈ ℤ ist a^{−1} = −a = (n − a) mod n.

6) Die Menge ℤ_{3} \ {0} = {1, 2} mit der Multiplikation a ∘ b = (a · b) mod 3 ist eine abelsche Gruppe mit dem neutralen Element 1. Die Inversen sind 1^{−1} = 1 und 2^{−1} = 2:

\begin{matrix}∘ & 1 & 2 \\ 1 & 1 & 2 \\ 2 & 2 & 1 \end{matrix}

7) Die Menge ℤ_{4} \ {0} = {1, 2, 3} mit der Multiplikation a ∘ b = (a · b) mod 4 ist keine Gruppe. Aus der Gruppentafel erkennt man, dass 1 der einzige Kandidat für das neutrale Element ist, es aber zu a = 2 keine Inverse gibt:

\begin{matrix}∘ & 1 & 2 & 3 \\ 1 & 1 & 2 & 3 \\ 2 & 2 & 0 & 2 \\ 3 & 3 & 2 & 1 \end{matrix}

Ein Ring ist eine Menge, in der man addieren und multiplizieren kann:

Definition 1.4: (Ring)

Eine Menge R mit zwei binären Verknüpfungen ⊕ (die “Addition”) und ⊗ (die “Multiplikation”) heißt “Ring”, wenn

a) (R, ⊕) eine abelsche Gruppe ist,

b) ⊗ eine assoziative Verknüpfung ist: (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) ∀ a, b, c ∈ R,

c) das Distributivgesetz

a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c), (a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c)

für alle a, b, c ∈ R gilt.

Ist ⊗ eine kommutative Verknüpfung (also a ⊗ b = b ⊗ a ∀ a, b ∈ R), so spricht man von einem “kommutativen Ring”.

Bemerkung 1.5: Für das neutrale Elemente 0 der Addition gilt in einem Ring immer 0 · r = r · 0 = 0 ∀r ∈ R, denn

0 · r = (0 + 0) · r = 0 · r + 0 · r.

Subtrahiert man auf beiden Seiten 0 · r, so erhält man 0 = 0 · r. Im nichtkommutativen Fall hat man sich auch 0 = r · 0 ∀r ∈ R zu überlegen, was analog folgt.

Beispiel 1.6: In den folgenden Beispielen seien + und · die übliche Addition bzw. Multiplikation in ℤ, ℚ, ℝ:

1) (ℤ, + , ·) ist ein kommutativer Ring.

2) (ℚ, + , ·) ist ein kommutativer Ring.

3) (ℝ, + , ·) ist ein kommutativer Ring.

4) Für jedes n ∈ ℕ ist die Menge ℤ_{n} = {0, 1, …, n − 1} mit der Addition a ⊕ b = (a + b) mod n und der Multiplikation a ⊗ b = (a · b) mod n ein kommutativer Ring. Um dies einzusehen, ist im Wesentlichen nur zu verifizieren, dass in der Tat das Distributivgesetz

(a · (b + c)) mod n = (((a · b) mod n) + ((a · c) mod n)) mod n

für ganze Zahlen a, b, c gilt. Die Details ersparen wir uns hier.

Ein Körper ist eine Menge, in der man addieren und multiplizieren kann (der also ein Ring ist), aber zusätzlich auch noch Division erlaubt:

Definition 1.7: (Körper)

Eine Menge K mit zwei binären Verknüpfungen ⊕ (die “Addition”) und ⊗ (die “Multiplikation”) heißt “Körper”, wenn

a) (K, ⊕, ⊗) ein Ring ist,

b) (K \ {0}, ⊗) eine Gruppe ist.

Hierbei ist mit 0 das neutrale Element bzgl. der Addition ⊕ gemeint. Die Division ist dann für jedes b ≠ 0 definiert als a/b := a ⊗ b^{−1}, wo b^{−1} die Inverse von b ∈ K \ {0} bzgl. ⊗ ist.

Zusätzlich zu den Ringeigenschaften gelten bei einem Körper also die beiden folgenden Eigenschaften:

• Es muss ein neutrales Element der Multiplikation existieren (meist mit 1 bezeichnet),

• zu jedem a ∈ K muss eine multiplikative Inverse a^{−1} mit a ⊗ a^{−1} = a^{−1} ⊗ a = 1 existieren (das wir dann als a^{−1} = 1/a schreiben).

Beispiel 1.8: In den folgenden Beispielen seien + und · die übliche Addition bzw. Multiplikation in ℤ, ℚ, ℝ:

1) (ℤ, + , ·) ist zwar ein Ring, aber kein Körper (die Division zweier ganzen Zahlen ergibt eine rationale Zahl, die in der Regel nicht ganzzahlig sein wird).

2) (ℚ, + , ·) ist ein Körper (zu jeder rationalen Zahl ≠ 0 gibt es eine multiplikative Inverse, nämlich den Kehrwert).

3) (ℝ, + , ·) ist ein Körper (zu jedem a ≠ 0 ist a^{−1} = 1/a ∈ ℝ definiert).

4) Die Restklassenringe ℤ_{n} mit der üblichen Arithmetik modulo n ∈ ℕ sind zwar stets Ringe, aber – abhängig von n – nicht unbedingt Körper. Nach Beispiel 1.3.6) ist die Multiplikation auf ℤ_{3} \{0} eine Gruppenstruktur, damit ist ℤ_{3} ein Körper. Nach Beispiel 1.3.7) ist die Multiplikation auf ℤ_{4} \ {0} keine Gruppenstruktur, damit ist ℤ_{4} lediglich ein Ring, aber kein Körper. Wie der folgende Satz besagt, liegt dies daran, dass 3 eine Primzahl ist, 4 aber nicht.

Satz 1.9: (Für welche p ist ℤ_{p} ein Körper?)

ℤ_{p} ist genau dann ein Körper, wenn p eine Primzahl ist. Die multiplikative Inverse von a ∈ ℤ_{p} \ {0} ist dann gegeben durch a^{−1} = a^{p−2}.

Beweis: Sei p eine Primzahl. Nach dem kleinen Satz von Fermat gilt

Für jedes a ∈ ℤ gilt a^{p−1} mod p = 1, falls p nicht a teilt.

Die Primzahl p teilt a ∈ {1, 2, …, p − 1} nicht, also gilt

a · a^{p−2} = a^{p−2} · a = 1 (mod p).

Wir interpretieren a als Element von ℤ_{p} = {0, 1, …, p − 1} mit der Addition und Multiplikation modulo p. Dann besagt die obige Gleichung, dass das Inverse von a ≠ 0 bzgl. der Multiplikation mod p durch a^{p−2} gegeben ist.

Ist p keine Primzahl, gilt p = f_{1} · f_{2} mit Faktoren f_{1}, f_{2} ∈ {1, 2, …, p − 1}. Interpretieren wir f_{1}, f_{2} als Elemente von ℤ_{p}, so gilt bzgl. der modularen Multiplikation f_{1} ·f_{2} = p mod p = 0. Wäre ℤ_{p} ein Körper, würde f_{1} = (f_{1} ·f_{2})·f_{2}^{−1} = 0 · f_{2}^{−1} = 0 folgen, was der Annahme f_{1} ∈ {1, 2, …, p − 1} widerspricht.

Q.E.D.

1.2 Repeated Squaring

Wie berechnet man möglichst effizient eine Potenz x^{n} einer Zahl x? Natürlich kann man Schritt für Schritt

p_{1} := x; p_{2} := x · p_{1}; p_{3} := x · p_{2}; …; p_{n} := x · p_{n−1}

berechnen (p_{n} = x^{n} ist das gesuchte Ergebnis), braucht dafür aber n − 1 Multiplikationen. In Anwendungen der Kryptographie etc. geht es darum, solche Multiplikationen für sehr große Werte von n zu ermitteln, da sollte man sich tunlichst überlegen, wie das Potenzieren schneller zu erledigen ist. Die Idee ist einfach, geschickt auf Zwischenergebnisse zurückzugreifen. So ist x^{8} z.B. mit nur 3 Multiplikationen

p_{1} := x; p_{2} := p_{1} · p_{1}; p_{4} := p_{2} · p_{2}; p_{8} := p_{4} · p_{4}

zu berechnen, für x^{21} braucht man 6 Multiplikationen:

p_{1} := x; p_{2} := p_{1} · p_{1}; p_{4} := p_{2} · p_{2}; p_{5} := x · p_{4};
p_{10} := p_{5} · p_{5}; p_{20} := p_{10} · p_{10}; p_{21} := x · p_{20}

Der wesentliche Schritt besteht also aus dem Quadrieren des letzten Zwischenergebnisses (damit erreicht man für n = 2er-Potenz immer das Endergebnis). Ist n keine Zweierpotenz, sind gelegentlich Multiplikationen mit x dazwischenzuschalten. Systematisch berechnet man sich die Binärdarstellung

n = 2^{k} + b_{k−1} · 2^{k−1} + ⋯ + b_{1} · 2^{1} + b_{0} · 2^{0}

des Exponenten mit den “Bits” b_{i} ∈ {0, 1}, z.B. durch (MuPAD-Code):

>> n := 21: // als Beispiel
>> m := n:
>> k := trunc(log(2, n)):
>> for i from 0 to k do
     b[i]:= m mod 2;
     m:= m div 2;  // = trunc(m/2)
   end_for:
>> b[i] $ i = 0..k;
                        1, 0, 1, 0, 1

(oder einfacher über numlib::g adic(n, 2)). Es ergibt sich folgender Potenzierungsalgorithmus:

Algorithmus “Repeated Squaring” 1.10:

Zu berechnen ist x^{n} mit n ∈ ℕ.

1: Bestimme die Binärdarstellung n = 2^{k} + ∑_{i=0}^{k−1} b_{i} · 2^{i} mit b_{i} ∈ {0, 1}.

2: Setze y := x.

3: Für i = k − 1, k − 2, ..., 1, 0 wiederhole:

Falls b_{i} = 0, setze y := y^{2}; Sonst setze y := y^{2} · x;

4: Ergebnis: y hat den Wert x^{n}.

Beweis der Korrektheit: wir zeigen, dass y am Ende des Schrittes 3 mit gegebenem i den Wert y = x^{[n/2^{i}]} hat (damit liegt für i = 0 das Endergebnis y = x^{[n/2^{0}]} = x^{n} vor). Induktionsstart: Am Ende des ersten Schritts mit i = k − 1 gilt y = x^{2}, falls b_{k−1} = 0 gilt bzw. y = x^{3}, falls b_{k−1} = 1. Die Exponenten von x stimmen überein mit

[\frac{n}{2^{k−1}} ] = [\frac{1}{2^{k−1}} · (2^{k} + b_{k−1} · 2^{k−1} + b_{k−2} · 2^{k−2} + ⋯)]
= [2 + b_{k−1} + b_{k−2} · \frac{1}{2} + ⋯]
= 2 + b_{k−1} = \{ \begin{matrix}2 & falls b_{k−1} = 0, \\ 3 & falls b_{k−1} = 1. \end{matrix}

Induktionsschritt: zu Beginn des Schrittes 3 habe y den Wert x^{[n/2^{i+1}]}. Nun wird der Schritt mit dem Wert i durchlaufen. Am Ende des Schrittes 3 hat wird y durch den Wert

\begin{matrix}y^{2} & falls b_{i} = 0, \\ y^{2} · x & falls b_{i} = 0 \end{matrix} \} = \{ \begin{matrix}x^{2·[n/2^{i+1}]} & falls b_{i} = 0, \\ x^{2·[n/2^{i+1}]+1} & falls b_{i} = 1 \end{matrix} \} = x^{2·[n/2^{i+1}]+b_{i}} (#)

überschrieben. Es gilt

2 · [\frac{n}{2^{i+1}} ] + b_{i} = 2 · [\frac{1}{2^{i+1}} · (2^{k} + b_{k−1} · 2^{k−1} + b_{k−2} · 2^{k−2} + ⋯)] + b_{i}

= 2 · [2^{k−i−1} + b_{k−1} · 2^{k−1−i−1} + ⋯ + b_{i+1} + \underbrace{b_{i} · \frac{1}{2} + ⋯}_{Nachkommastellen}] + b_{i}

= 2 · (2^{k−i−1} + b_{k−1} · 2^{k−2−i} + ⋯ + b_{i+1}) + b_{i}
= 2^{k−i} + b_{k−1} · 2^{k−1−i} + ⋯ + b_{i+1} · 2 + b_{i}.

Dies stimmt überein mit

[\frac{n}{2^{i}} ] = [\frac{1}{2^{i}} · (2^{k} + b_{k−1} · 2^{k−1} + b_{k−2} · 2^{k−2} + ⋯)]

= [2^{k−i} + b_{k−1} · 2^{k−1−i} + ⋯ + b_{i+1} · 2 + b_{i} + \underbrace{b_{i+1} · \frac{1}{2} + ⋯}_{Nachkommastellen}]

= 2^{k−i} + b_{k−1} · 2^{k−1−i} + ⋯ + b_{i+1} · 2 + b_{i}.

Also hat der vom Schritt 3 des Algorithmus gelieferte Wert (#) die Darstellung

x^{2·[n/2^{i+1}]+b_{i}} = x^{[n/2^{i}]}.

Q.E.D.

Bemerkung 1.11: Das Entscheidende am Algorithmus ist der Rechenaufwand:

↓18.11.04

er besteht für n = 2^{k} aus lediglich k Multiplikationen. Allgemein braucht man für 2^{k} ≤ n < 2^{k+1} maximal 2 · k Multiplikationen (für n = 2^{k+1} − 1 mit der Binärdarstellung n = 11 … 1_{2} braucht man genau 2 · k Multiplikationen). Für die Anzahl M(n) der Multiplikationen gilt also stets

k ≤ M(n) ≤ 2 · k,

also mit k = [log_{2}(n)]:

[log_{2}(n)] ≤ M(n) ≤ 2 · [log_{2}(n)].

Ganz grob:

Durch Repeated Squaring wird x^{n} mit maximal 2 · log_{2}(n) Multiplikationen berechnet.

Man beachte, dass log_{2}(n) für großes n sehr viel kleiner ist als n.

Bemerkung 1.12: Der Algorithmus ist immer anwendbar, wenn irgendwelche Multiplikationen (oder Gruppenverknüpfungen) zu berechnen sind. So kann beispielsweise x ein Element von ℤ_{n} sein, die Multiplikationen wären dann als modulare Multiplikationen durchzuführen.

Anwendung (Berechnung von Inversen mod p) 1.13:

Nach Satz 1.9 sind für jede Primzahl p die multiplikativen Inversen im Körper ℤ_{p} durch a^{−1} = a^{p−2} gegeben, d.h., die Division duch a ist die Multiplikation mit a^{p−2}. Hierbei läßt sich a^{p−2} per Repeated Squaring mit maximal 2 · log_{2}(p − 2) modularen Multiplikationen berechnen.

1.3 Der Euklidische Algorithmus

Es geht nun um das effiziente Berechnen von \underline{g}rößten \underline{g}emeinsamen \underline{T}eilern (ggT oder engl. gcd = \underline{g}reatest \underline{c}ommon \underline{d}ivisor). Für ganze Zahlen ist dieses Konzept aus der Schule bekannt. Wir verallgemeinern den Begriff für Ringstrukturen, denn neben ganzen Zahlen wollen wir später auch Polynome behandeln. Zunächst die Begriffe der Teilbarkeit und des ggT in einem Ring:

Definition 1.14: (Teilbarkeit in allgemeinen Ringen)

Sei R ein beliebiger Ring. Dann heißt a ∈ R ein “Teiler”^{1} von b ∈ R (geschrieben a | b), falls es ein r ∈ R gibt mit b = r · a.

Definition 1.15: (größter gemeinsamer Teiler)

Sei R ein beliebiger Ring. Dann heißt c ∈ R ein “größter gemeinsamer Teiler”^{2} von a, b ∈ R \ {0}, geschrieben als c = ggT(a, b), falls c | a und c | b gilt und für alle r ∈ R mit r | a und r | b stets r | c folgt.

Bemerkung 1.16: I.A. ist der ggT nicht eindeutig. So kann man z.B. auf dem Ring ℤ den ggT (6, 9) als 3 oder auch als −3 vereinbaren.

Vereinbarung: Wir machen den ggT auf dem Ring ℤ eindeutig, indem wir ggT (a, b) > 0 fordern ∀a, b ∈ ℤ \ {0}.

Bemerkung 1.17: In MuPAD ist gcd(a, b) der Aufruf zur Berechnung von ggT(a, b):

>> gcd(123456, 54321)
                               3

Für den Euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier Ringelemente braucht man eine gewisse Ordnungsstruktur. Die Ordnungsstruktur ist versteckt in der folgenden Abbildung d:

Definition 1.18: (Euklidischer Ring)

Ein Ring R heißt Euklidischer Ring, wenn es eine Abbildung d : R → {0, 1, 2, …} mit d(0) = 0 gibt, sodass stets “Division mit Rest” durchführbar ist: zu jedem Paar a, b ∈ R mit b ≠ 0 existiere q, r ∈ R mit

a = q · b + r, d(r) < d(b).

Hierbei heisst q der “Quotient” von a durch b (geschrieben als q = a div b) und r der “Rest” (geschrieben als a mod b).

1Für b = 0 ist offensichtlich jedes Ringelement ein Teiler.

2Für a = 0 bzw. b = 0 setze ggT (0, b) = b bzw. ggT (a, 0) = a. Wir werden im Folgenden jedoch nur den ggT von Ringelementen ≠ 0 betrachten.

Beispiel 1.19:

1) Der Ring ℤ der ganzen Zahlen ist ein Euklidischer Ring mit d(n) = |n|. Nämlich:

a div b = [\frac{a}{b}] , a mod b = a − b · [\frac{a}{b}] .

Nach Definition von [ ] gilt hierbei : [\frac{a}{b}] ≤ \frac{a}{b} < [\frac{a}{b}] + 1, woraus für b > 0

b · [\frac{a}{b}] ≤ a < b · [\frac{a}{b}] + b ⇒ 0 ≤ a − b · [\frac{a}{b}] < b

bzw. für b < 0

b · [\frac{a}{b}] ≥ a > b · [\frac{a}{b}] + b ⇒ 0 ≥ a − b · [\frac{a}{b}] > b

folgt, also in jedem Fall |a mod b| < |b|. Wir verwenden später ständig die fundamentale Eigenschaft

0 ≤ a mod b < b für positive b ∈ ℤ.

2) Wir werden bald den Ring der Polynome p = c_{n}·x^{n}+c_{n−1}x^{n−1}+…+c_{0} betrachten, der auch ein Euklidischer Ring ist. Hier betrachtet man d(p) = Polynomgrad von p.

Bemerkung 1.20: Offensichtlich ist in einem Euklidischen Ring die Teilbarkeit a | b äquivalent zu b mod a = 0.

Lemma 1.21:

Mit Vereinbarung 1.16 gilt im Euklidischen Ring ℤ:

ggT (a, b) = ggT (a mod b, b) ∀a, b ∈ ℤ \ {0}.

Beweis: Division mit Rest liefert a = q · b + r mit r = a mod b. Sei c = ggT (a, b). Es gilt c | a und c | b, damit muss c auch r = a − q · b teilen. Damit teilt c den Wert c′ := ggT (r, b), da dieser größter gemeinsamer Teiler von r und b ist. Andererseits gilt c′ | r und c′ | b, damit muss c′ auch a = q · b + r teilen. Damit teilt c′ den Wert c = ggT (a, b), da dieser größter gemeinsamer Teiler von a und b ist. Also: c | c′ und c′ | c. Diese Aussage gilt für einen beliebigen Euklidischen Ring. Mit Vereinbarung 1.16 gilt c > 0, c′ > 0 auf ℤ. Auf diesem speziellen Ring folgt aus der Teilbarkeit 0 < c ≤ c′ und 0 < c′ ≤ c und damit c = c′.

Q.E.D.

Wie berechnet man nun den ggT zweier ganzer Zahlen, ohne mühsam alle Teiler der Zahlen bestimmen zu müssen? Wir betracheten ggT (a, b) mit a > b > 0. Mit Lemma 1.21 können wir die Größe der Zahlen leicht reduzieren, indem wir statt ggT (a, b) einfach ggT (a mod b, b) berechnen, wobei a mod b < b gilt. Es macht keinen Sinn, weiterzugehen und nun (a mod b) mod b zu bilden, denn

\underbrace{(a mod b)}_{∈\{0,1,...,b−1\}} mod b = a mod b.

Mit der offensichtlichen Symmetrie ggT (x, y) = ggT (y, x) können wir aber die Zahlen mittels b mod (a mod b) weiter reduzieren:

ggT (\underbrace{r_{1}}_{a}, \underbrace{r_{2}}_{b}) = ggT (r_{2}, \underbrace{r_{1} mod r_{2}}_{r_{3}}) = ggT (r_{3}, \underbrace{r_{2} mod r_{3}}_{r_{4}}) = · · · .

Es ergeben sich so Zahlen r_{0} > r_{1} > r_{2} > r_{3} > … ≥ 0. Irgendwann muss eine dieser Zahlen notwendigerweise 0 werden, d.h., man findet

r_{i+1} = r_{i−1} mod r_{i} = 0,

was bedeutet, dass r_{i} | r_{i−1} gilt. In diesem Fall gilt aber ggT (r_{i−1}, r_{i}) = r_{i} und wir sind fertig: der ggT ist berechnet. Die folgende Form des klassischen Euklidischen Algorithmus ignoriert die Vorzeichen von a, b ∈ ℤ und berechnet ggT (a, b) als ggT (|a|, |b|):

Euklidischer Algorithmus 1.22:

Zu berechnen ist ggT (a, b) mit a, b ∈ ℤ \ {0}.

1: Setze r_{0} := max(|a|, |b|); r_{1} := min(|a|, |b|).

2: Für i = 1, 2, … wiederhole r_{i+1} := r_{i−1} mod r_{i};

bis r_{i+1} = 0 eintritt.

3: Ergebnis: r_{i} = ggT (a, b).

Beweis der Korrektheit: Die i-Schleife in 2) muss abbrechen, da die ganzzahligen Werte r_{i} streng monoton abnehmen und nicht negativ werden können. Nach Lemma 1.21 gilt in jedem Schritt

ggT (r_{i}, r_{i+1}) = ggT (r_{i}, r_{i−1} mod r_{i}) = ggT (r_{i}, r_{i−1}) = ggT (r_{i−1}, r_{i}).

Ist r_{i+1} = 0, so gilt 0 = r_{i−1} mod r_{i}, also ggT (r_{i−1}, r_{i}) = r_{i}.

Q.E.D.

Satz 1.23: (Laufzeit des Euklidischen Algorithmus)

Der Euklidische Algorithmus 1.22 für a, b ∈ ℤ \ {0} benötigt maximal 1 + 2 · log_{2}(min(|a|, |b|)) Wiederholungen von Schritt 2).

Beweis Es sei n die Anzahl der Schritte, die der Euklidische Algorithmus im Schritt 2) benötigt, bis er auf r_{n+1} = 0 trifft und r_{n} = ggT (a, b) ausgibt. In Schritt 2) wird jeweils durch Division mit Rest r_{i+1} = r_{i−1} mod r_{i} berechnet, wobei mit q_{i} = r_{i−1} div r_{i} gilt:

r_{i−1} = q_{i} · r_{i} + r_{i+1}.

Mit r_{i−1} > r_{i} gilt q_{i} ≥ 1, also r_{i−1} ≥ r_{i} + r_{i+1} > 2 · r_{i+1}. Hieraus folgt

∏_{i=2}^{n−1} r_{i−1} > 2^{n−2} · ∏_{i=2}^{n−1} r_{i+1}

und mit r_{1} > r_{2}, r_{n−1} > r_{n} ≥ 1:

2^{n−2} < \frac{∏_{i=2}^{n−1} r_{i−1}}{∏_{i=2}^{n−1} r_{i+1}} = \frac{r_{1} · r_{2}}{r_{n−1} · r_{n}} < \frac{r_{1}^{2}}{r_{n−1} · r_{n}} < \frac{r_{1}^{2}}{2} ⟹ 2^{n−1} < r_{1}^{2}.

Anwendung von log_{2} auf die letzte Ungleichung liefert n − 1 < log_{2}(r_{1}^{2}) = 2 · log_{2}(r_{1}), wobei r_{1} = min(|a|, |b|).

Q.E.D. ↓24.11.04

Bemerkenswerterweise läßt sich der ggT zweier Zahlen stets als “Linearkombination” dieser Zahlen ausdrücken: es gibt stets (von a und b abhängige) ganze Zahlen s und t mit

ggT (a, b) = s · a + t · b.

Diese Linearkombination kann durch eine Erweiterung des Euklidischen Algorithmus 1.22 berechnet werden:

Erweiterter Euklidischer Algorithmus 1.24:

Seien a, b ∈ ℤ mit |a| ≥ |b| > 0.

1: Setze r_{0} := |a|; s_{0} := sign(a); t_{0} := 0; r_{1} := |b|; s_{1} := 0; t_{1} := sign(b); wobei sign(x) = 1 für x > 0 und sign(x) = −1 für x < 0.

2: Für i = 1, 2, … wiederhole:

Berechne q_{i} := r_{i−1} div r_{i};

Setze r_{i+1} := r_{i−1} − q_{i} · r_{i} (also r_{i+1} = r_{i−1} mod r_{i}); Setze s_{i+1} := s_{i−1} − q_{i} · s_{i}; Setze t_{i+1} := t_{i−1} − q_{i} · t_{i};

bis r_{i+1} = 0 eintritt.

3: Ergebnis: r_{i} = ggT (a, b) und es gilt r_{i} = s_{i} · a + t_{i} · b.

Beweis der Korrektheit: Der Algorithmus terminiert und liefert ggT (a, b) analog zu Algorithmus 1.22. Es bleibt nur zu zeigen, dass für alle i in Schritt 2) gilt:

r_{i} = s_{i} · a + t_{i} · b.

Für i = 0 und i = 1 ist die Behauptung klar per Definition von r_{0}, s_{0}, t_{0} und r_{1}, s_{1}, t_{1}. Für i ≥ 2 folgt per Induktion:

s_{i} · a + t_{i} · b = (s_{i−2} − q_{i−1} · s_{i−1}) · a + (t_{i−2} − q_{i−1} · t_{i−1}) · b
= (s_{i−2} · a + t_{i−2} · b) − q_{i−1} · (s_{i−1} · a + t_{i−1} · b)
= r_{i−2} − q_{i−1} · r_{i−1}
= r_{i}.

Q.E.D.

Bemerkung 1.25: Die Laufzeitabschätzung 1.23 gilt natürlich unverändert.

1.4 Berechnung modularer Inverser

Wir wollen uns nun noch einmal mit dem Ring ℤ_{n} = {0, …, n − 1} mit der Arithmetik modulo n beschäftigen. Im Rahmen des RSA-Verfahrens sind wir an den sogenannten “Einheiten” modulo n interessiert. Dies sind die Zahlen, die bezgl. der Multiplikation modulo n invertierbar sind, d.h., für die eine multiplikative Inverse k^{−1} ∈ ℤ_{n} existiert mit

k^{−1} · k mod n = 1.

Solch eine Inverse existiert genau dann, wenn ggT (k, n) = 1 gilt (d.h., wenn k und n “teilerfremd” sind):

Lemma 1.26: (Charakterisierung modularer Inverser)

Für n ∈ ℕ gilt: k ∈ ℤ_{n} \ {0} ist genau dann invertierbar bzgl. der Multiplikation modulo n, wenn ggT (k, n) = 1 gilt.

Beweis: Es sei k ∈ ℤ_{n} \ {0} invertierbar, d.h., es gibt ein k^{−1} ∈ ℤ_{n} mit k^{−1} · k mod n = 1, d.h., k^{−1} · k = m · n + 1 für ein m ∈ ℕ. Damit gilt k^{−1} · k − m · n = 1. Der ggT (k, n) teilt sowohl k als auch n und ist damit auch Teiler der Differenz beliebiger Vielfacher von k und n. Also teilt ggT (k, n) die Zahl 1 und es folgt ggT (k, n) = 1.

Umgekehrt liefert für k mit ggT (k, n) = 1 der Erweiterte Euklidische Algorithmus 1.24 die Darstellung 1 = s · k + t · n mit s, t ∈ ℤ. Reduktion modulo n liefert

1 = s · k mod n

und damit s mod n als multiplikative Inverse von k modulo n.

Q.E.D.

Es ergibt sich als Korollar unmittelbar das schon aus Satz 1.9 bekannte Ergebnis, dass ℤ_{p} ein Körper ist, wenn p eine Primzahl ist: in diesem Fall sind nämlich alle Werte k ∈ {1, 2, …, p − 1} teilerfremd zu p und damit nach Lemma 1.26 invertierbar. Der Beweis des obigen Lemmas 1.26 ist konstruktiv (nämlich k^{−1} = s mod n) und liefert uns unmittelbar den folgenden Algorithmus zur Berechnung modularer Inverser. Er ist so formuliert, dass das modulare Inverse k^{−1} modulo n berechnet wird, falls k invertierbar modulo n ist. Anderenfalls wird entschieden, dass k nicht invertierbar modulo n ist:

Berechnung des modularen Inversen 1.27:

Sei n ∈ ℕ und k ∈ ℤ_{n} \ {0}.

1: Berechne mit Hilfe des Erweiterten Euklidischen Algorithmus 1.24 die Darstellung g = ggT (k, n) = s · k + t · n.

2: Ergebnis: Ist g = 1, so gilt k^{−1} = s mod n.

Ist g ≠ 1, so ist k nicht invertierbar modulo n.

Dies liefert eine Alternative zur Berechnung von k^{−1} = k^{p−2} mod p gemäß Satz 1.9, die gemäß der Bemerkungen 1.11 und 1.25 einen ähnlichen Rechenaufwand erfordert.