Sie sind hier:

Der Erweiterte Euklidische Algorithmus

Der Erweiterte Euklidische Algorithmus - Exkurs „Diophantische Gleichungen“

Zur Bestimmung des multiplikativen Inversen in mod ist im allgemeinen eine lineare Kongruenzgleichung zu lösen. Systematisch wird dies durch Anwendung des Erweiterten Euklidische Algorithmus erzielt. Der hierzu gehörende mathematische Hintergrund der diophantischen Gleichungen (s.u.) kann hierbei wertvolle mathematische Einsichten in umfangreichere Strukturen und v.a. auch in die Frage der Lösbarkeit linearer Kongruenzgleichungen ermöglichen und systematisches Denken schulen. Wird dies angestrebt, so kann als tiefergehende und allgemeinere Einbettung das Arbeitsblatt diophantische Gleichung bearbeitet werden. Hierbei wird das Auffinden von Lösungen, das Entdecken unendlich vieler Lösungen und ihrer Struktur schülerzentriert erarbeitet. Sollte dies nicht gewünscht werden, kann der Unterrichtsgang auch direkt mit der Erarbeitung des Erweiterten Euklidischen Algorithmus beginnen.

Zunächst jedoch einige Bemerkungen zum Exkurs:

Mathematischer Hintergrund: die diophantischen Gleichungen

Kurzer Exkurs: Dieser Unterrichtsinhalt ist vom Bildungsplan nicht gefordert.

Bei der Bestimmung des multiplikativen Inversen, das als Entschlüsselungszahl d beim Verschlüsseln mittels Multiplikation benötigt wird, muss der Spezialfall einer linearen diophantischen Gleichung gelöst werden.

Definition: Eine lineare diophantische Gleichung ist eine Gleichung der Form:

$a \cdot x + b \cdot y = c$

mit Variablen $x, y$ und Koeffizienten $a, b, c \in ℤ$ .

Forderung: Die Lösungen $x, y$ sollen ebenfalls ganzzahlig sein.

Anhand eines exemplarischen Beispiels kann man auch mit den SuS schnell erarbeiten, dass es unendlich viele Lösungen gibt und auch die Struktur dieser Lösungen ist relativ leicht durchschaubar, wenn man $y$ in Abhängigkeit von $x$ ausdrückt.

Geeignete Beispiele sind die folgenden Gleichungen mit ihren Lösungen:

Gleichung	Lösungen
$2 \cdot x + 1 \cdot y = 4$	$(0; 4), (1; 2), (2; 0), (- 1; 6), \dots, (z; 4 - 2 z)$
$3 \cdot x + 1 \cdot y = 2$	$(0; 2), (1; - 1), (2; - 4), (- 1; 5), \dots, (z; 2 - 3 z)$
$3 \cdot x + 2 \cdot y = 4$	$(0; 2), (2; - 1), (- 2; 5), \dots$

Die allgemeine Lösung ist bei der letzten Gleichung etwas schwerer einzusehen:

Bemerkung: Ein Zurückbesinnen auf die Inhalte der Einheit lineare Gleichungen und Funktionen in Klasse 7 kann hilfreich sein; auch dort wurden schon lineare Gleichungen der Form $a \cdot x + b \cdot y = c$ in die Form $y = m \cdot x + d$ .

Umformung (mit der Umbennenung $x = z$ zur Unterscheidung zwischen Lösung und Variable) ergibt $x = z; y = \frac{4 - 3 z}{2}$ . Hier ist $y$ genau dann ganzzahlig, wenn $4 - 3 z$ gerade ist, also wenn $z$ gerade ist, d.h. wenn $z = 2 k; k \in ℤ$ .

Es ergibt sich $y = \frac{4 - 3 \cdot 2 k}{2}; k \in ℤ$ . Damit lautet die allgemeine Lösung hier $(x; y) = (2 k; 2 - 3 k); k \in ℤ$ .

Jedoch sind nicht alle Gleichungen lösbar, z.B. $5 \cdot x + 10 \cdot y = 4$ . Umformung ergibt $x = z; y = \frac{4 - 5 z}{10}$ und $y$ ist also genau dann ganzzahlig, wenn gilt: $4 - 5 z = n \cdot 10 mit n \in ℤ$ . Systematisches Ausprobieren mit $z$ zeigt jedoch schnell, dass dies nicht erfüllbar ist. Damit besitzt diese diophantische Gleichung keine Lösungen.

Allgemein gilt der Satz:

Gegeben sei die diophantische Gleichung $a \cdot x + b \cdot y = c mit a, b, c \in ℤ$ .

Diese besitzt genau dann Lösungen $x, y \in ℤ$ , wenn gilt: $ggT (a; b) ∣ c$

Die Grundlage dieses Satzes ist als Lemma von Bézout bekannt. Dieser besagt, dass sich der $ggT (a; b)$ als Linearkombination darstellen lässt.

Der Beweis ist nicht sehr schwer, jedoch lohnt hier der Zeitaufwand eher nicht. Zur Vollständigkeit sei er hier jedoch angebracht:

$\textrm{„}\Rightarrow\textrm{“ : Sei }(x_{0},y_{0})\textrm{ eine Lösung von }a% \cdot x+b\cdot y=c,\textrm{ also gilt }a\cdot x_{0}+b·y_{0}=c.$ Klar ist: $\textrm{ggT}(a;b)|a\cdot x_{0}+b\cdot y_{0}$ , wie auch SuS leicht einsehen. Und da $a\cdot x_{0}+b\cdot y_{0}=c,$ folgt: $\mathrm{ggT}(a;b)|c.$

$\mathrm{„}\Leftarrow\mathrm{“ :ggT}(a;b)|c\Rightarrow∃q\in ℤ\mathrm{mit}c=q\cdot\mathrm{ggT}(a;b).$ Außerdem existiert nach dem Lemma von Bézout eine Linearkombination des $\mathrm{ggT}(a;b).$ (Argumentation durch Konstruktion: Diese liefert der Erweiterte Euklidische Algorithmus, s.u.). Also existiert $s\cdot x_{0}+r\cdot y_{0}=\textrm{ggT}(a;b).$ Multiplikation der Gleichung mit $h=\frac{c}{\mathrm{ggT}(a;b)}$ liefert die Behauptung. ∎

Anmerkung: Die Plausibilisierung, dass die Lösbarkeit etwas mit den Teilern von $a$ und $b$ zu tun hat, ließe sich durch Besprechung einiger Beispiele wie im obigen Beispiel $5 \cdot x + 10 \cdot y = 4$ und evtl. dem anschließenden forschenden Auftrag an die SuS: „Konstruiert diophantische Gleichungen, die keine Lösung besitzen. Auf was kommt es dabei an?“ erreichen.

Dieser Exkurs ist für die Unterrichtseinheit inhaltlich nicht zwingend notwendig. Wird darauf verzichtet, so kann das Arbeitsblatt diophantische Gleichung ausgelassen und gleich mit der Erarbeitung des Erweiterten Euklidischen Algorithmus' (wahlweise mit Arbeitsblatt Erweiterter Euklidischer Algorithmus, S-zentriert) fortgefahren werden.

Bemerkung: Es ergibt sich hiermit eine interessante Gelegenheit, auf die historischen Entwicklungen der Gleichungslehre zu sprechen zu kommen: Diophantos von Alexandria, nach dem die Gleichungen benannt sind, auf dessen Grabstein sich sogar eine Gleichung in verbalisierter Form befindet:

„Hier das Grabmal deckt Diophantos — ein Wunder zu schauen:

Durch des Entschlafenen Kunst lehrt dich sein Alter der Stein.
Knabe zu bleiben verlieh ein Sechstel des Lebens ein Gott ihm;
Fügend das Zwölftel hinzu, ließ er ihm sprossen die Wang;
Steckte ihm drauf auch an nach dem Siebtel die Fackel der Hochzeit,
Und fünf Jahre nachher teilt' er ein Söhnlein ihm zu.
Weh! unglückliches Kind, so geliebt! Halb hatt' es des Vaters
Alter erreicht, da nahms Hades, der schaurige, auf.
Noch vier Jahre den Schmerz durch Kunde der Zahlen besänft'gend
Langte am Ziele des Seins endlich er selber auch an.“

Algebraisierung: $x = \frac{x}{6} + \frac{x}{12} + \frac{x}{7} + 5 + \frac{x}{2} + 4$ ergibt die Lösung $x = 84$ .

Zurück zu den BP-Inhalten „Lösung linearer Kongruenzgleichungen und Erweiterter Euklidischer Algorithmus“:

Im Fall der reinen Bestimmung des multiplikativen Inversen ohne den Hintergrund der Lösbarkeitsfrage, die im Exkurs „diophantische Gleichungen“ angesprochen wurde, reduziert sich die Schwierigkeit: Die Bestimmungsgleichung des multiplikativen Inversen $e \cdot d \equiv 1 mod n$ lässt sich zur (diophantischen) Gleichung äquivalent umformen:

$e \cdot d \equiv 1 mod n \Leftrightarrow e \cdot d = k \cdot n + 1 \Leftrightarrow e \cdot d - k \cdot n = 1$

$d$ und $n$ sind dabei die Variablen der Gleichung.

Rückblickende Bemerkung zum Exkurs „diophantische Gleichungen“: Es gilt in unserem Kontext also stets $c = 1$ . Hiermit erhält die Lösungsbedingung der linearen diophantischen Gleichung die Form $ggT (e; n) ∣ 1$ , also gilt $ggT (e; n) = 1$ und damit: $e, n$ sind teilerfremd. Insbesondere ist dies erfüllt, wenn $e$ und $n$ Primzahlen sind.

Obwohl die Berechnung des $ggT (e; n)$ in diesem Kontext aufgrund der Wahl als Primzahlen nicht mehr nötig ist, sollte sie im Beispiel doch durchgeführt werden, da der Erweiterte Euklidische Algorithmus durch Zurückrechnen für Schüler durchschaubar aus dem Euklidischen Algorithmus entsteht.

Hierzu ist eine Wiederholung des Euklidischen Algorithmus' angebracht. Entsprechende Aufgaben sind im Arbeitsblatt enthalten. Ist eine ausführlichere Wiederholung nötig, so kann auf die Materialien von Klasse 8 zurückgegriffen werden.

Nach dieser wichtigen vorbereitenden Übung kann zur Erarbeitung des Erweiterten Euklidischen Algorithmus übergegangen werden.

Für die Herleitung eignet sich als Aufhängepunkt die kryptographische Kernaufgabe „gesucht wird das multiplikative Inverse $d$ zu $4 (mod 7)$ “:

$4 \cdot d \equiv 1 (mod 7) \Leftrightarrow 4 \cdot d - k \cdot 7 = 1$

Erster Schritt ist die Berechnung des $ggT (7; 4)$ mittels Euklidischem Algorithmus:

$\textrm{(i)}\quad 7=1\cdot 4+3$

$\textrm{(ii)}\quad 4=1\cdot 3+1$

$\textrm{(iii)}\quad 3=3\cdot 1+0$

( $1\textrm{ggT}$ , Abbruchbedingung). Optional in Matrixform:

\begin{matrix} 7 & 4 & 3 \\ 4 & 3 & 1 \\ 3 & 1 & 0 \end{matrix}

Ansatz des Erweiterten Euklidischen Algorithmus ist nun der folgende Gedanke: Die linke Seite der Gleichung $4·d–k·7=1$ stellt eine Linearkombination der „ $1$ “ mittels der Zahlen $7$ und $4$ dar und es sollen nun die Koeffizienten $d$ und $k$ bestimmt werden.

Dies löst man durch Rückwärtsrechnen:

Zeile $1\textrm{(ii)}$ , aufgelöst nach $1$ : $1=4–1\cdot 3\quad\textrm{(*)}$

Bemerkung: Die gesuchte „ $4$ “ taucht schon auf, „ $3$ “ muss ersetzt werden.

Nun eine Zeile höher: Zeile $1\textrm{(ii)}$ , aufgelöst nach $3$ ergibt: $3=7–4$ . Dies wird nun in $(*)$ eingesetzt: $1=4–1\cdot 3$

$\Rightarrow 1=4–1·(7–4)=4–7+4$

Sortieren ergibt: $1=2\cdot 4+(-1)\cdot 7=2\cdot 4-1\cdot 7$

Unsere lineare Kongruenzgleichung $4\cdot d–k\cdot 7=1$ besitzt die Lösungen $d=2$ und $k=1$ . Wir benötigen davon lediglich $d=2$ .

Bemerkung: Auf dem Arbeitsblatt Erweiterter Euklidischer Algorithmus, S-zentriert ist dieses Vorgehen für die SuS ausführlich und übersichtlich dargestellt.

Ergebnis: Das multiplikative Inverse zu $4$ bezüglich $(\textrm{mod }7)$ ist $d=2$ .

Bemerkungen dazu:

Eine Erarbeitung des Algorithmus im Unterrichtsgespräch ist angeraten, da gerade das Zurückrechnen und die dabei nötigen Gedanken und der notwendige Überblick, die letztendlich zum Erfolg bei der Erstellung der Linearkombination führen, eine Führung nötig erscheinen lassen. Gruppen, denen ein eigenständiges Erarbeiten des Themas zuzutrauen ist, können mit dem Arbeitsblatt Erweiterter Euklidischer Algorithmus, S-zentriert an das Thema herangehen.
Im Beispiel oben ist die Bestimmung des $1\textrm{ggT}$ und damit auch die Bestimmung des multiplikativen Inversen mit wenigen Schritten erledigt. Bei einer Berechnung mit größerer Schrittanzahl gilt es noch mehr, die Übersicht nicht zu verlieren. Eine ausgedehntere Übungsphase mit Beispielen aufsteigender Komplexität ist hier unerlässlich, damit SuS lernen, das Ziel nicht aus den Augen zu verlieren. Je nach Schülergruppe ist es angeraten, ein mehrschrittiges Beispiel noch einmal gemeinsam durchzurechnen. Hierzu eignet sich z.B. die auf dem Arbeitsblatt genannte Aufgabe $9\cdot d\equiv 1(\textrm{mod }33)$ .
Ein möglicher Tafelaufschrieb:
Die Matrixschreibweise ist als vereinfachte Schreibweise beim Euklidischen Algorithmus machbar. Beim Durchführen der Erweiterung jedoch erscheint hier die Gefahr des Verständnisverlustes zu hoch, die schrittweise Umformung der Gleichungen hilft den SuS, den Ablauf zu verinnerlichen und den Überblick zu behalten.
Wurde der Exkurs „Diophantische Gleichungen“ nicht vorgenommen, so genügt es für den Zusammenhang mit der Kryptographie, den Erweiterten Euklidischen Algorithmus wie auf Arbeitsblatt Erweiterter Euklidischer Algorithmus, S-zentriert einzuführen: „Der EEA liefert für eine Gleichung der Form $a\cdot x+b\cdot y=\textrm{ggT}(a;b)$ mit $a,b\in\mathbf{N}$ (neben dem $\textrm{ggT}(a;b)$ als Zwischenergebnis) die Lösungen $x,y\in ℤ$ .“ Mit dieser Feststellung wird klar, warum auf dem Euklidischen Algorithmus aufgebaut wird. Organisch folgt aus dem kryptographischen Kontext die Gleichung $e\cdot d–k\cdot n=1$ . Besonderes Augenmerk sollte dabei auch auf das Vorzeichen von $k$ gelegt werden. Selbstverständlich kann die Umformung auch anders vorgenommen werden, damit die Identifikation der entstehenden Gleichung mit der Standardform der linearen Kongruenzgleichung $a\cdot x+b\cdot y=\textrm{ggT}(a;b)$ leichter ist. Hier sollte nach eigenem Ermessen, jedoch im weiteren Unterrichtsverlauf konsequent verfahren werden.
Die Erstellung weiterer Übungsaufgaben (die auch noch schwerer zu erraten sind → Sinnhaftigkeit des Algorithmus) ist denkbar einfach:

Ansatzpunkt ist die Forderung $\textrm{ggT}(a;b)=1$ ( $a, b$ teilerfremd; am leichtesten zu realisieren durch Aufstellen einer entsprechenden Primzahlzerlegung). Dann lautet die Aufgabe „finde $d$ so, dass $a\cdot d\equiv 1(\textrm{mod }b)$ “. Die Bearbeitung dieser Umkehraufgabe kann eine gute binnendifferenzierende Aufgabe sein (Übung Nr.3 auf dem Arbeitsblatt).

Unterrichtsverlauf: Herunterladen [odt][244 KB]

Unterrichtsverlauf: Herunterladen [pdf][615 KB]

Weiter zu Exkurse

Der Er­wei­ter­te Eu­kli­di­sche Al­go­rith­mus