Der verlängerte Euklidische Algorithmus ist eine Erweiterung auf den Euklidischen Algorithmus. Außer der Entdeckung des größten allgemeinen Teilers von ganzen Zahlen a und b, wie der Euklidische Algorithmus tut, findet es auch ganze Zahlen x und y (von denen einer normalerweise negativ ist), die die Identität von Bézout befriedigen

:

Der verlängerte Euklidische Algorithmus ist besonders nützlich, wenn a und b coprime sind, da x das multiplicative Gegenteil eines modulo b ist, und y das multiplicative Gegenteil von b modulo a ist.

Informelle Formulierung des Algorithmus

Um die Erweiterung des Algorithmus von Euklid zu illustrieren, denken Sie die Berechnung von gcd (120, 23), der auf dem Tisch links gezeigt wird. Bemerken Sie, dass der Quotient in jeder Abteilung ebenso neben dem Rest registriert wird.

In diesem Fall zeigt der Rest in der vierten Linie (der 1 gleich ist) an, dass der gcd 1 ist; d. h. 120 und 23 sind coprime (auch hat relativ erst genannt). Wegen der Einfachheit ist das gewählte Beispiel ein coprime Paar; aber der allgemeinere Fall von gcd außer 1 auch Arbeiten ähnlich.

Es gibt zwei Methoden, das beides Verwenden des Abteilungsalgorithmus weiterzugehen, der getrennt besprochen wird.

Wiederholende Methode

Diese Methode schätzt Ausdrücke der Form für den Rest in jedem Schritt des Euklidischen Algorithmus. Jede aufeinander folgende Zahl kann als der Rest der Abteilung vorherigen zwei solcher Zahlen geschrieben werden, welcher Rest mit dem ganzen Quotienten q dieser Abteilung wie folgt ausgedrückt werden kann:

:

Durch den Ersatz gibt das:

: der geschrieben werden kann

:

Die ersten zwei Werte sind die anfänglichen Argumente für den Algorithmus:

::

So brechen die Koeffizienten als auf, und, und andere durch gegeben werden

::

Der Ausdruck für den letzten Nichtnullrest gibt die gewünschten Ergebnisse, da diese Methode jeden Rest in Bezug auf a und b, wie gewünscht, schätzt.

Beispiel: Schätzen Sie den GCD 120 und 23.

Die Berechnung geht wie folgt weiter:

Die letzte Linie liest 1 = 120 × 9 + 23 × 47, der die erforderliche Lösung ist: x = 9 und y = 47.

Da sich der GCD erweist, 1 zu sein, bedeutet das auch, dass 47 das multiplicative Gegenteil 23 in modulo 120, und auch gibt, dass in modulo 23, 9 (oder 14, der dasselbe Element vertritt) das multiplicative Gegenteil 120 (oder gleichwertig 5) gibt.

:47 × 23  1 (mod 120) und auch 9 × 120 14 × 5  1 (mod 23).

Für eine ganze Zahl, um invertible modulo b zu sein, ist es notwendig, dass a und b, coprime so sein wenn ein GCD größerer als 1 gefunden wird, man kann beschließen, dass solch ein Modulgegenteil nicht besteht.

Bemerken Sie, dass die Gleichungen, die die Werte x definieren, von denjenigen unabhängig sind, die die Werte y definieren, und dass die Identität von Bézout am Ende gefunden

hat:

erlaubt, y abzuleiten, wenn x bekannt ist. Man kann deshalb die Werte y aus der Berechnung weglassen (obwohl sie nützlich sein können, um für rechenbetonte Fehler zu überprüfen). Das ist für Anwendungen, wie Computerwissenschaft von Modulgegenteilen besonders wichtig, die den Wert nur eines Koeffizienten von Bézout verlangen.

Rekursive Methode

Diese Methode versucht, die ursprüngliche Gleichung direkt, durch das Reduzieren der Dividende und des Teilers allmählich von der ersten Linie bis die letzte Linie zu lösen, die dann mit dem trivialen Wert und der Arbeit rückwärts eingesetzt werden kann, um die Lösung zu erhalten.

Denken Sie die ursprüngliche Gleichung:

Bemerken Sie, dass die Gleichung unverändert nach dem Zerlegen der ursprünglichen Dividende in Bezug auf den Teiler plus ein Rest und dann Umgruppierung von Begriffen bleibt. Wenn wir eine Lösung der Gleichung in der zweiten Linie haben, dann können wir rückwärts arbeiten, um x und y, wie erforderlich, zu finden. Obwohl wir die Lösung noch der zweiten Linie nicht haben, wie der Umfang der Begriffe vermindert (120 und 23 bis 23 und 5) bemerken. Folglich, wenn wir fortsetzen, das anzuwenden, schließlich werden wir die letzte Linie erreichen, die offensichtlich (1, 0) als eine triviale Lösung hat. Dann können wir rückwärts arbeiten und allmählich x und y herausfinden.

Zum Zweck, diese Methode zu erklären, wird das volle Arbeiten nicht gezeigt. Stattdessen werden einige der sich wiederholenden Schritte beschrieben, um den Grundsatz hinter dieser Methode zu demonstrieren.

Anfang, indem es jede Linie vom ersten Tisch mit dem Abteilungsalgorithmus umgeschrieben wird, sich auf die Dividende dieses Mal konzentrierend (weil wir die Dividende einsetzen werden).

Tabellenmethode

Die Tabellenmethode, auch bekannt als "Der Magische Kasten", sind wahrscheinlich die einfachste Methode, mit einem Bleistift und Papier auszuführen. Es ist der wiederholenden Methode ähnlich, obwohl es nicht direkt verlangt, dass Algebra verwendet. Die Hauptidee ist, an die Gleichungskette zu denken

:

als eine Folge von Teilern. Im laufenden Beispiel haben wir die Folge 120, 23, 5, 3, 2, 1. Jedes Element in dieser Kette kann als eine geradlinige Kombination des Originals und am meisten namentlich geschrieben werden, das letzte Element kann auf diese Weise geschrieben werden. Die Tabellenmethode schließt das Halten eines Tisches jedes Teilers, schriftlich als eine geradlinige Kombination ein. Der Algorithmus fängt mit dem Tisch wie folgt an:

:

Die Elemente in der Säule des Tisches werden die Teiler in der Folge sein. Jeder kann als die geradlinige Kombination vertreten werden

:

Und Werte sind für die ersten zwei Reihen des Tisches offensichtlich, die vertreten und sie. Um für irgendwelchen zu rechnen, bemerken Sie das

:

Denken. Dann muss es das sein

: und

:

Das ist leicht, algebraisch mit einem einfachen Ersatz nachzuprüfen.

Wirklich würde das Ausführen der Tabellenmethode, obwohl einfacher ist als die obengenannten Gleichungen, anzeigen. Um die dritte Reihe des Tisches im Beispiel zu finden, bemerken Sie gerade, dass 120 geteilte durch 23 5mal plus ein Rest gehen. Das gibt uns k, den multiplizierenden Faktor für diese Reihe. Jetzt ist jeder Wert im Tisch der Wert zwei Reihen darüber, minus k Zeiten der Wert sofort darüber. Das führt richtig

zu

:

: und

:

Nach dem Wiederholen dieser Methode, jede Linie des Tisches zu finden (bemerken, dass der Rest, der im Tisch und dem multiplizierenden Faktor geschrieben ist, zwei verschiedene Zahlen ist!), die Endwerte dafür und wird lösen:

:

Diese Methode ist einfach, nur die wiederholte Anwendung einer Regel verlangend, und verlässt die Antwort in der Endreihe des Tisches ohne Zurückverfolgen.

Bemerken Sie auch, dass, wenn Sie vorhaben, ein Modulgegenteil für einen modulo b zu finden, und Sie mit x enden negativ zu sein, müssen Sie dann das Modul b zu x hinzufügen, um es in die Reihe zu bringen

Formelle Beschreibung des Algorithmus

Wiederholende Methode

Durch die alltägliche Algebra der Erweiterung und Gruppierung wie Begriffe (beziehen sich, um Abteilung zu dauern), wird der folgende Algorithmus für die wiederholende Methode erhalten:

1. Wenden Sie Euklidischen Algorithmus an, und lassen Sie q (n Anfänge von 1) eine begrenzte Liste von Quotienten in der Abteilung sein.
2. Initialisieren Sie x, x als 1, 0, und y, y als 0,1 beziehungsweise.
3. Dann für jeden ich, so lange q, definiert wird
4. Schätzen Sie x = x − qx
5. Schätzen Sie y = y − qy
6. Wiederholen Sie den obengenannten nach dem Erhöhen ich durch 1.
7. Die Antworten sind von x und y zweit-zu-letzt.

Der Pseudocode für diese Methode wird unten gezeigt:

fungieren Sie extended_gcd (a, b)

x: = 0 lastx: = 1

y: = 1 lasty: = 0

während b  0

Quotient: = ein div b

(a, b): = (b, ein mod b)

(x, lastx): = (lastx - quotient*x, x)

(y, lasty): = (lasty - quotient*y, y)

kehren Sie (lastx, lasty) zurück

Extraschritte sind erforderlich, wenn man mit negativem a und/oder b arbeitet.

Rekursive Methode

Den allgemeinen Fall der Gleichung in der letzten entsprechenden Abteilung, den folgenden Algorithmus-Ergebnissen lösend. In Anbetracht jedes Paares von natürlichen Zahlen a, b, findet es, dass ganze Zahlen x, y solch schätzen, dass Axt + dadurch nichtnegativ ist und sowohl a als auch b teilt, der andeutet, dass es der größte allgemeine Teiler von a und b ist.

1. Wenn b = 0, die Algorithmus-Enden, die Lösung x = 1, y = 0 zurückgebend.
2. Sonst:
3. * Bestimmen den Quotienten q und Rest r davon, durch b das Verwenden des Abteilungsalgorithmus der ganzen Zahl zu teilen.
4. * finden Dann rekursiv Koeffizienten s, t solch, dass Bakkalaureus der Naturwissenschaften + rt sowohl b als auch r teilt.
5. * Schließlich gibt der Algorithmus die Lösung x = t, und y = s  qt zurück.

Das kann im Pseudocode wie folgt geschrieben werden:

fungieren Sie extended_gcd (a, b)

wenn b = 0

kehren Sie (1, 0) zurück

sonst

(q, r): = teilen sich (a, b)

(s, t): = extended_gcd (b, r)

kehren Sie (t, s - q * t) zurück

Das nimmt an, dass ein "teilen" Verfahren besteht, der (Quotient, Rest) Paar zurückkehrt (man konnte q wechselweise stellen: = ein div b, und dann r = ein  b * q).

Beweis der Genauigkeit

Lassen Sie a und b natürliche Zahlen sein. Wir möchten beweisen, dass der Algorithmus, und Umsatz (x, y) solch endet, dass Axt + dadurch sowohl a als auch b teilt. Wir gehen durch die Induktion auf b weiter.

• Wenn b = 0, dann endet der Algorithmus sofort mit x = 1 und y = 0, so Axt + durch = a; das ist klar nichtnegativ und teilt sowohl a als auch 0 (als 0a = 0).
• Lassen Sie sonst q, r bei der Abteilung durch b als in der Algorithmus-Beschreibung, so = bq + r und r &lt erhalten werden; b durch die Eigenschaften des Abteilungsalgorithmus.
• Die Ungleichheit r < b bedeutet, dass wir die Induktionsvoraussetzung für (b, r) im Platz (a, b) anwenden können, und das versichert, dass die rekursive Anwendung endet.
• Lassen Sie (s, t), die Werte zu sein, die es zurückgibt; durch die Induktion wissen wir, dass Bakkalaureus der Naturwissenschaften + rt nichtnegativ ist und sowohl b als auch r teilt.
• Jetzt gibt der Algorithmus x = t und y = s  qt zurück. Wir haben Axt + durch = an + b (s  qt) = Bakkalaureus der Naturwissenschaften + (ein  bq) t = Bakkalaureus der Naturwissenschaften + rt, der (noch) nichtnegativ ist und sowohl b als auch r teilt. Dieselbe Zahl teilt deshalb auch r + bq = a, der den Beweis begrenzt.

Der Beweis zeigt, dass der rekursive Algorithmus angepasst werden kann, um sich mit willkürlichen ganzen Zahlen a, b mit gerade einer geringen Modifizierung zu befassen: Im endenden Fall b = 0 sollte es das Zeichen von a prüfen, und wenn es negative Rückkehr x = 1 statt x = 1 ist, um sicherzustellen, dass Axt + dadurch immer nichtnegativ ist. Das nimmt wirklich an, dass der Abteilungsalgorithmus arbeitet, wenn a und/oder b negativ sind, und dem |r &lt sichert; |b in allen Fällen (verlangt die übliche Spezifizierung des Abteilungsalgorithmus tatsächlich, dass r nichtnegativ ist, aber das ist im Beweis nicht notwendig, der jetzt durch das Wiederauftreten auf |b ist).

Die Computerwissenschaft eines multiplicative Gegenteils in einem begrenzten Feld

Der verlängerte Euklidische Algorithmus kann auch verwendet werden, um das multiplicative Gegenteil in einem begrenzten Feld zu berechnen.

Pseudocode

In Anbetracht des nicht zu vereinfachenden Polynoms f (x) hat gepflegt, das begrenzte Feld und das Element (x) zu definieren, dessen Gegenteil, dann eine Form des Algorithmus gewünscht wird, der passend ist für zu beschließen, dass das Gegenteil durch das folgende gegeben wird.

ZEICHEN: Rest und Quotient ist Funktionen, die vom Reihe-Rest [] und Quotient [] verschieden sind. Rest bezieht sich auf den Rest, wenn zwei Zahlen geteilt werden, und sich Quotient auf den Quotienten der ganzen Zahl bezieht, wenn zwei Zahlen geteilt werden. Abteilung (mit dem Rest) muss in Bezug auf die polynomische Arithmetik und nicht als mit "normalen" Zahlen berechnet werden.

Pseudocode:

Rest [1]: = f (x)

Rest [2]: = (x)

Hilfs-[1]: = 0

Hilfs-[2]: = 1

i: = 2

während Rest [ich]> 1

i: = ich + 1

Rest [ich]: = Rest (Rest [i-2] / Rest [i-1])

Quotient [ich]: = Quotient (Rest [i-2] / Rest [i-1])

Hilfs-[ich]: = - Quotient [ich] * Hilfs-[i-1] + Hilfs-[i-2]

Gegenteil: = Hilfs-[ich]

Bemerken

Minus das Zeichen ist für einige begrenzte Felder im Schritt nicht notwendig.

Hilfs-[ich]: = - Quotient [ich] * Hilfs-[i-1] + Hilfs-[i-2]

Das ist seitdem im begrenzten Feld-GF (2), zum Beispiel wahr, Hinzufügung und Subtraktion sind dasselbe. Mit anderen Worten, 1 ist sein eigenes zusätzliches Gegenteil in GF (2). Das kommt in jedem begrenzten Feld-GF (2) vor, wo n eine ganze Zahl ist.

Beispiel

Zum Beispiel, wenn das Polynom, das verwendet ist, um den begrenzten Feld-GF (2) zu definieren, f (x) = x + x + x + x + 1 ist, und x + x + x + 1 = {53} in der großen-endian hexadecimal Notation das Element ist, dessen Gegenteil gewünscht wird, dann läuft das Durchführen des Algorithmus auf den folgenden hinaus:

</tr>

</tr></tr></tr></tr></tr></Tisch>

:Note: Die Hinzufügung in einem binären begrenzten Feld ist XOR.

So ist das Gegenteil x + x + x + x = {CA}, wie durch das Multiplizieren der zwei Elemente zusammen bestätigt werden kann.

Der Fall von mehr als 2 Zahlen

Man kann den Fall von mehr als 2 Zahlen wiederholend behandeln. Zuerst zeigen wir das. Um sich zu erweisen, hat das gelassen. Definitionsgemäß gcd ist ein Teiler und. So für einige. Ähnlich ist ein Teiler so für einige. Lassen. Durch unseren Aufbau dessen, aber seitdem ist der größte Teiler ist eine Einheit. Und da das Ergebnis bewiesen wird.

So, wenn dann es gibt und solch, dass so die Endgleichung sein wird

:

Um so, dann für n Zahlen zu gelten, verwenden wir Induktion

:

mit den Gleichungen im Anschluss an direkt.

Siehe auch

• Euklidisches Gebiet
• Geradliniger Kongruenz-Lehrsatz
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Seiten 859-861 des Abschnitts 31.2: Größter allgemeiner Teiler.

Links

• Die Quelle für die Form des Algorithmus hat gepflegt, das multiplicative Gegenteil in GF zu bestimmen (2^8)