Erweiterter euklidischer Algorithmus - Extended Euclidean algorithm

In der Arithmetik und Computerprogrammierung ist der erweiterte euklidische Algorithmus eine Erweiterung des euklidischen Algorithmus und berechnet neben dem größten gemeinsamen Teiler (gcd) der ganzen Zahlen a und b auch die Koeffizienten der Bézout-Identität , die ganze Zahlen x und y . sind so dass

${\displaystyle ax+by=\gcd(a,b).}$

Dies ist ein zertifizierender Algorithmus , da der gcd die einzige Zahl ist, die diese Gleichung gleichzeitig erfüllen und die Eingaben teilen kann. Es ermöglicht auch, fast ohne zusätzliche Kosten die Quotienten von a und b durch ihren größten gemeinsamen Teiler zu berechnen .

Der erweiterte euklidische Algorithmus bezieht sich auch auf einen sehr ähnlichen Algorithmus zum Berechnen des polynomischen größten gemeinsamen Teilers und der Koeffizienten der Bézout-Identität zweier univariater Polynome .

Die erweiterten Euklidischen Algorithmus ist insbesondere nützlich , wenn a und b sind coprime . Mit dieser Vorkehrung ist x die modulare multiplikative Inverse von a modulo b und y die modulare multiplikative Inverse von b modulo a . In ähnlicher Weise ermöglicht der polynomial erweiterte euklidische Algorithmus die Berechnung der multiplikativen Inversen in algebraischen Körpererweiterungen und insbesondere in endlichen Körpern nichtprimer Ordnung. Daraus folgt, dass beide erweiterten euklidischen Algorithmen in der Kryptographie weit verbreitet sind . Insbesondere die Berechnung des modularen multiplikativen Inversen ist ein wesentlicher Schritt bei der Ableitung von Schlüsselpaaren im RSA -Verschlüsselungsverfahren mit öffentlichem Schlüssel.

Beschreibung

Der euklidische Standardalgorithmus geht von einer Folge von euklidischen Divisionen aus, deren Quotienten nicht verwendet werden. Nur die Reste bleiben erhalten. Für den erweiterten Algorithmus werden die sukzessiven Quotienten verwendet. Genauer gesagt besteht der euklidische Standardalgorithmus mit a und b als Eingabe darin, eine Folge von Quotienten und eine Folge von Resten zu berechnen, so dass ${\displaystyle q_{1},\ldots,q_{k}}$${\displaystyle r_{0},\ldots ,r_{k+1}}$

${\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i- 1}-q_{i}r_{i}\quad {\text{und}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(dies definiert }}q_ {i})\\&\,\,\,\vdots \end{ausgerichtet}}}$

Es ist die Haupteigenschaft der euklidischen Division, dass die Ungleichungen auf der rechten Seite eindeutig und aus und${\displaystyle q_{i}}$${\displaystyle r_{i+1}}$${\displaystyle r_{i-1}}$${\displaystyle r_{i}.}$

Die Berechnung stoppt, wenn man einen Rest von Null erreicht; der größte gemeinsame Teiler ist dann der letzte Rest ungleich null${\displaystyle r_{k+1}}$${\displaystyle r_{k}.}$

Der erweiterte euklidische Algorithmus geht ähnlich vor, fügt jedoch zwei weitere Folgen hinzu, wie folgt

${\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}& =1\\&\,\,\,\vdots &&\,\,\,\vdots\\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\ text{und }}0&\leq r_{i+1}<|r_{i}|&{\text{(dies definiert }}q_{i}{\text{)}}\\s_{i+1} &=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\ ,\vdots \end{ausgerichtet}}}$

Die Berechnung stoppt auch, wenn und gibt ${\displaystyle r_{k+1}=0}$

• ${\displaystyle r_{k}}$ist der größte gemeinsame Teiler der Eingabe und${\displaystyle a=r_{0}}$${\displaystyle b=r_{1}.}$
• Die Bézout-Koeffizienten sind und das heißt${\displaystyle s_{k}}$${\displaystyle t_{k},}$${\displaystyle \gcd(a,b)=r_{k}=as_{k}+bt_{k}}$
• Die Quotienten von a und b durch ihren größten gemeinsamen Teiler sind gegeben durch und${\displaystyle s_{k+1}=\pm {\frac {b}{\gcd(a,b)}}}$${\displaystyle t_{k+1}=\pm {\frac {a}{\gcd(a,b)}}}$

Wenn a und b beide positiv sind und , dann ${\displaystyle \gcd(a,b)\neq \min(a,b)}$

${\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{und}}\quad |t_{ i}|\leq\left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor}$

denn wobei bezeichnet den ganzzahligen Teil von x , also die größte ganze Zahl nicht größer als x . ${\displaystyle 0\leq i\leq k,}$${\displaystyle \lfloor x\rfloor}$

Dies impliziert, dass das Paar von Bézout-Koeffizienten, das durch den erweiterten euklidischen Algorithmus bereitgestellt wird, das minimale Paar von Bézout-Koeffizienten ist, da es das eindeutige Paar ist, das beide oben genannten Ungleichungen erfüllt.

Es bedeutet auch, dass der Algorithmus ohne Ganzzahlüberlauf von einem Computerprogramm ausgeführt werden kann , das Ganzzahlen einer festen Größe verwendet, die größer als die von a und b ist .

Beispiel

Die folgende Tabelle zeigt, wie der erweiterte euklidische Algorithmus mit den Eingaben 240 und 46 vorgeht . Der größte gemeinsame Teiler ist der letzte Eintrag ungleich Null, 2 in der Spalte "Rest". Die Berechnung endet bei Zeile 6, da der Rest darin 0 ist . Bézout-Koeffizienten erscheinen in den letzten beiden Einträgen der vorletzten Zeile. Tatsächlich lässt sich leicht nachweisen, dass −9 × 240 + 47 × 46 = 2 ist . Schließlich sind die letzten beiden Einträge 23 und –120 der letzten Zeile bis auf das Vorzeichen die Quotienten der Eingänge 46 und 240 durch den größten gemeinsamen Teiler 2 .

Nachweisen

Als Folge der ist eine absteigende Folge von nichtnegativen ganzen Zahlen (ab i = 2). Es muss also mit einigen aufhören. Dies beweist, dass der Algorithmus irgendwann aufhört. ${\displaystyle 0\leq r_{i+1}<|r_{i}|,}$${\displaystyle r_{i}}$${\displaystyle r_{k+1}=0.}$

Da der größte gemeinsame Teiler für und gleich ist. Dies zeigt, dass der größte gemeinsame Teiler der Eingabe der gleiche ist wie der von. Dies beweist, dass der größte gemeinsame Teiler von a und b ist . (Bis zu diesem Punkt ist der Beweis derselbe wie der des klassischen euklidischen Algorithmus.) ${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i},}$${\displaystyle (r_{i-1},r_{i})}$${\displaystyle (r_{i},r_{i+1}).}$${\displaystyle a=r_{0},b=r_{1}}$${\displaystyle r_{k},r_{k+1}=0.}$${\displaystyle r_{k}}$

Als und gilt für i = 0 und 1. Die Beziehung folgt durch Induktion für alle : ${\displaystyle a=r_{0}}$${\displaystyle b=r_{1},}$${\displaystyle as_{i}+bt_{i}=r_{i}}$${\displaystyle i>1}$

${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i}=(as_{i-1}+bt_{i-1})-(as_{i}+bt_{ i})q_{i}=(as_{i-1}-as_{i}q_{i})+(bt_{i-1}-bt_{i}q_{i})=as_{i+1} +bt_{i+1}.}$

Somit sind und Bézout-Koeffizienten. ${\displaystyle s_{k}}$${\displaystyle t_{k}}$

Betrachten Sie die Matrix

${\displaystyle A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}.}$

Die Rekursionsbeziehung kann in Matrixform umgeschrieben werden

${\displaystyle A_{i+1}=A_{i}\cdot {\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}.}$

Die Matrix ist die Identitätsmatrix und ihre Determinante ist eins. Die Determinante der Matrix ganz rechts in der vorhergehenden Formel ist −1. Daraus folgt , dass die Determinante ist insbesondere für wir haben dies als eine Bézout Identität angesehen haben , dies zeigt , dass und sind coprime . Die Beziehung , die oben und erwiesenermaßen Euclid Lemma zeigt , dass dividieren b und teilt ein . Da sie coprime sind, sind sie bis auf ihr Vorzeichen die Quotienten von b und a durch ihren größten gemeinsamen Teiler. ${\displaystyle A_{1}}$${\displaystyle A_{i}}$${\displaystyle (-1)^{i-1}.}$${\displaystyle i=k+1,}$${\displaystyle s_{k}t_{k+1}-t_{k}s_{k+1}=(-1)^{k}.}$${\displaystyle s_{k+1}}$${\displaystyle t_{k+1}}$${\displaystyle as_{k+1}+bt_{k+1}=0}$${\displaystyle s_{k+1}}$${\displaystyle t_{k+1}}$

Um die letzte Behauptung zu beweisen, nehmen Sie an, dass a und b beide positiv sind und . Dann , und wenn , kann gesehen werden , dass die s und t Sequenzen für ( a , b ) im Rahmen des EEA sind, bis zur anfänglichen 0s und 1s, die t und s - Sequenzen für ( b , a ). Die Definitionen zeigen dann, dass der Fall ( a , b ) auf den Fall ( b , a ) reduziert wird. Gehen Sie also davon aus, ohne die Allgemeingültigkeit zu verlieren. ${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle a\neq b}$${\displaystyle a<b}$${\displaystyle a>b}$

Es ist ersichtlich, dass 1 und (die durch existiert ) eine negative ganze Zahl ist. Danach wechseln sich Vorzeichen und strikte Größenzunahme ab, was sich induktiv aus den Definitionen und der Tatsache ergibt, dass für , weil der Fall gilt . Das gleiche gilt aus dem gleichen Grund für die nach den ersten paar Begriffen. Außerdem ist dies leicht zu erkennen (wenn a und b beide positiv sind und ). Daher, ${\displaystyle s_{2}}$${\displaystyle s_{3}}$${\displaystyle \gcd(a,b)\neq \min(a,b)}$${\displaystyle s_{i}}$${\displaystyle q_{i}\geq 1}$${\displaystyle 1\leq i\leq k}$${\displaystyle i=1}$${\displaystyle a>b}$${\displaystyle t_{i}}$${\displaystyle q_{k}\geq 2}$${\displaystyle \gcd(a,b)\neq \min(a,b)}$

${\displaystyle |s_{k+1}|=\left|{\frac {b}{\gcd(a,b)}}\right|\geq 2|s_{k}|\qquad {\text{und }}\qquad |t_{k+1}|=\left|{\frac {a}{\gcd(a,b)}}\right|\geq 2|t_{k}|.}$

Dies, einhergehend mit der Tatsache, dass in absoluten Werten größer oder gleich alle vorherigen bzw. abgeschlossenen Beweise sind. ${\displaystyle s_{k},t_{k}}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$

Polynom erweiterter euklidischer Algorithmus

Für univariate Polynome mit Koeffizienten in einem Körper funktioniert alles ähnlich, euklidische Division, Bézouts Identität und erweiterter euklidischer Algorithmus. Der erste Unterschied besteht darin, dass bei der euklidischen Division und dem Algorithmus die Ungleichung durch eine Gradungleichung ersetzt werden muss. Ansonsten bleibt alles, was in diesem Artikel vorangeht, gleich, indem man einfach ganze Zahlen durch Polynome ersetzt. ${\displaystyle 0\leq r_{i+1}<|r_{i}|}$${\displaystyle \deg r_{i+1}<\deg r_{i}.}$

Ein zweiter Unterschied liegt in der Begrenzung der Größe der Bézout-Koeffizienten, die durch den erweiterten euklidischen Algorithmus bereitgestellt wird, der im polynomiellen Fall genauer ist und zu dem folgenden Satz führt.

Wenn a und b zwei von Null verschiedene Polynome sind, dann erzeugt der erweiterte euklidische Algorithmus das eindeutige Paar von Polynomen ( s , t ) mit

${\displaystyle as+bt=\gcd(a,b)}$

und

${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}$

Ein dritter Unterschied besteht darin, dass im polynomiellen Fall der größte gemeinsame Teiler nur bis zur Multiplikation mit einer von Null verschiedenen Konstanten definiert ist. Es gibt mehrere Möglichkeiten, einen größten gemeinsamen Teiler eindeutig zu definieren.

In der Mathematik ist es üblich, dass der größte gemeinsame Teiler ein monisches Polynom ist . Um dies zu erhalten, genügt es, jedes Element der Ausgabe durch den führenden Koeffizienten von zu teilen. Dies erlaubt, dass, wenn a und b teilerfremd sind, man 1 auf der rechten Seite der Bézout-Ungleichung erhält. Andernfalls kann man jede von Null verschiedene Konstante erhalten. In der Computeralgebra haben die Polynome gewöhnlich ganzzahlige Koeffizienten, und diese Art der Normalisierung des größten gemeinsamen Teilers führt zu viele Brüche ein, um praktisch zu sein. ${\displaystyle r_{k}.}$

Die zweite Möglichkeit, den größten gemeinsamen Teiler im Fall von Polynomen mit ganzzahligen Koeffizienten zu normalisieren, besteht darin, jede Ausgabe durch den Inhalt von zu dividieren , um einen primitiven größten gemeinsamen Teiler zu erhalten. Wenn die Eingangspolynome teilerfremd sind, liefert diese Normalisierung auch einen größten gemeinsamen Teiler gleich 1. Der Nachteil dieses Ansatzes besteht darin, dass viele Brüche berechnet und während der Berechnung vereinfacht werden sollten. ${\displaystyle r_{k},}$

Ein dritter Ansatz besteht darin, den Algorithmus der sich ergebenden Pseudo-Rest-Sequenzen in einer Weise zu erweitern, die der Erweiterung des euklidischen Algorithmus auf den erweiterten euklidischen Algorithmus ähnlich ist. Dies ermöglicht, dass ausgehend von Polynomen mit ganzzahligen Koeffizienten alle berechneten Polynome ganzzahlige Koeffizienten haben. Außerdem ist jeder berechnete Rest ein unterresultierendes Polynom . Insbesondere wenn die Eingangspolynome teilerfremd sind, wird die Identität von Bézout ${\displaystyle r_{i}}$

${\displaystyle as+bt=\operatorname {Res} (a,b),}$

wobei die Resultierende von a und b bezeichnet . In dieser Form von Bézouts Identität gibt es keinen Nenner in der Formel. Dividiert man alles durch das Resultierende, erhält man die klassische Bézout-Identität mit einem expliziten gemeinsamen Nenner für die darin vorkommenden rationalen Zahlen. ${\displaystyle \operatorname {Res} (a,b)}$

Pseudocode

Um den oben beschriebenen Algorithmus zu implementieren, ist zunächst anzumerken, dass bei jedem Schritt nur die beiden letzten Werte der indizierten Variablen benötigt werden. Um Speicher zu sparen, muss daher jede indizierte Variable durch nur zwei Variablen ersetzt werden.

Der Einfachheit halber verwendet der folgende Algorithmus (und die anderen Algorithmen in diesem Artikel) parallele Zuweisungen . In einer Programmiersprache, die diese Funktion nicht besitzt, müssen die parallelen Zuweisungen mit einer Hilfsvariable simuliert werden. Zum Beispiel der erste,

(old_r, r) := (r, old_r - quotient * r)

ist äquivalent zu

prov := r;
r := old_r - quotient × prov;
old_r := prov;

und ähnlich für die anderen parallelen Aufgaben. Dies führt zu folgendem Code:

function extended_gcd(a, b)
    (old_r, r) := (a, b)
    (old_s, s) := (1, 0)
    (old_t, t) := (0, 1)
    
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
        (old_t, t) := (t, old_t − quotient × t)
    
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

Der Quotient von a und b durch ihren größten gemeinsamen Teiler, der ausgegeben wird, kann ein falsches Vorzeichen haben. Dies ist am Ende der Berechnung leicht zu korrigieren, wurde hier aber nicht gemacht, um den Code zu vereinfachen. In ähnlicher Weise ist, wenn entweder a oder b null ist und das andere negativ ist, der größte gemeinsame Teiler, der ausgegeben wird, negativ, und alle Vorzeichen der Ausgabe müssen geändert werden.

Beachten Sie schließlich, dass man in Bézouts Identität , nach gegeben auflösen kann . Eine Optimierung des obigen Algorithmus besteht also darin, nur die Folge zu berechnen (die den Bézout-Koeffizienten ergibt ) und dann am Ende zu berechnen : ${\displaystyle ax+by=\gcd(a,b)}$${\displaystyle y}$${\displaystyle a,b,x,\gcd(a,b)}$${\displaystyle s_{k}}$${\displaystyle x}$${\displaystyle y}$

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := (old_r − old_s × a) div b
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

Doch in vielen Fällen ist dies nicht wirklich eine Optimierung: Während der frühere Algorithmus nicht anfällig für Überlauf ist , wenn sie mit Maschinen ganzen Zahlen verwendet (dh, ganze Zahlen mit einem festen oberen Ziffern gebunden), die Multiplikation von old_s a * bei der Berechnung von bezout_t kann überlaufen, wodurch diese Optimierung auf Eingaben beschränkt wird, die in weniger als der Hälfte der maximalen Größe dargestellt werden können. Bei der Verwendung von ganzen Zahlen unbegrenzter Größe wächst der Zeitaufwand für Multiplikation und Division quadratisch mit der Größe der ganzen Zahlen. Dies impliziert, dass die "Optimierung" eine Folge von Multiplikationen/Divisionen von kleinen ganzen Zahlen durch eine einzelne Multiplikation/Division ersetzt, was mehr Rechenzeit erfordert als die Operationen, die sie zusammengenommen ersetzt.

Vereinfachung von Brüchen

Eine Fraktion ein/Bwenn in kanonischer vereinfachter Form a und b sind coprime und b positiv ist. Diese kanonisch vereinfachte Form erhält man, indem man die drei Ausgangszeilen des vorhergehenden Pseudocodes durch . ersetzt

if s = 0 then output "Division by zero"
if s < 0 then s := −s;  t := −t   (for avoiding negative denominators)
if s = 1 then output -t        (for avoiding denominators equal to 1)
output -t/s

Der Beweis dieses Algorithmus beruht auf der Tatsache , dass s und t sind zwei coprime solche ganze Zahlen, die als + bt = 0 , und somit . Um die kanonisch vereinfachte Form zu erhalten, genügt es, das Minuszeichen zu verschieben, um einen positiven Nenner zu haben. ${\displaystyle {\frac {a}{b}}=-{\frac {t}{s}}}$

Wenn b a gleichmäßig teilt , führt der Algorithmus nur eine Iteration aus und wir haben s = 1 am Ende des Algorithmus. Dies ist der einzige Fall, in dem die Ausgabe eine ganze Zahl ist.

Berechnen multiplikativer Inversen in modularen Strukturen

Der erweiterte euklidische Algorithmus ist das wesentliche Werkzeug zum Berechnen multiplikativer Inversen in modularen Strukturen, typischerweise die modularen ganzen Zahlen und die algebraischen Felderweiterungen . Ein bemerkenswertes Beispiel für den letzteren Fall sind die endlichen Körper nicht-primer Ordnung.

Modulare ganze Zahlen

Wenn n eine positive ganze Zahl ist, kann der Ring Z / n Z mit der Menge {0, 1, ..., n -1} der Reste der euklidischen Division durch n identifiziert werden , wobei die Addition und die Multiplikation darin bestehen, die Rest um n des Ergebnisses der Addition und der Multiplikation von ganzen Zahlen. Ein Element a von Z / n Z hat eine multiplikative Inverse ( dh es ist eine Einheit ), wenn es zu n teilerfremd ist . Insbesondere dann , wenn n ist prime , a hat einen multiplikativen Inversen , wenn es nicht Null ist (modulo n ). Somit Z / n Z ist ein Feld , wenn und nur wenn n eine Primzahl ist.

Die Identität von Bézout behauptet, dass a und n genau dann teilerfremd sind, wenn es ganze Zahlen s und t gibt, so dass

${\displaystyle ns+at=1}$

Reduzieren dieser Identität modulo n ergibt

${\displaystyle at\equiv 1\mod n.}$

Somit ist t oder genauer der Rest der Division von t durch n die multiplikative Inverse von a modulo n .

Um den erweiterten euklidischen Algorithmus an dieses Problem anzupassen, sollte man beachten, dass der Bézout-Koeffizient von n nicht benötigt wird und somit nicht berechnet werden muss. Um ein Ergebnis zu erhalten, das positiv und kleiner als n ist , kann man auch die Tatsache verwenden, dass die vom Algorithmus bereitgestellte ganze Zahl t | . erfüllt t | < n . Das heißt, wenn t < 0 ist , muss am Ende n hinzugefügt werden . Dies führt zu dem Pseudocode, bei dem die Eingabe n eine ganze Zahl größer als 1 ist.

 function inverse(a, n)
    t := 0;     newt := 1
    r := n;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (t, newt) := (newt, t − quotient × newt) 
        (r, newr) := (newr, r − quotient × newr)

    if r > 1 then
        return "a is not invertible"
    if t < 0 then
        t := t + n

    return t

Einfache algebraische Felderweiterungen

Der erweiterte euklidische Algorithmus ist auch das Hauptwerkzeug zur Berechnung multiplikativer Inversen in einfachen algebraischen Körpererweiterungen . Ein wichtiger Fall, der in der Kryptographie und Codierungstheorie weit verbreitet ist, sind endliche Körper nichtprimer Ordnung. Tatsächlich ist, wenn p eine Primzahl ist und q = p ^d , der Körper der Ordnung q eine einfache algebraische Erweiterung des Primkörpers von p Elementen, erzeugt durch eine Wurzel eines irreduziblen Polynoms vom Grad d .

Eine einfache algebraische Erweiterung L eines Körpers K , erzeugt durch die Wurzel eines irreduziblen Polynoms p vom Grad d, kann mit dem Quotientenring identifiziert werden , und seine Elemente sind in bijektiver Übereinstimmung mit den Polynomen vom Grad kleiner als d . Die Addition in L ist die Addition von Polynomen. Die Multiplikation in L ist der Rest der euklidischen Division durch p des Produkts der Polynome. Um die Arithmetik in L zu vervollständigen , bleibt also nur noch zu definieren, wie multiplikative Inverse berechnet werden. Dies geschieht durch den erweiterten euklidischen Algorithmus. ${\displaystyle K[X]/\langle p\rangle,}$

Der Algorithmus ist dem oben zur Berechnung der modularen multiplikativen Inversen bereitgestellten sehr ähnlich. Es gibt zwei wesentliche Unterschiede: Erstens wird die vorletzte Zeile nicht benötigt, da der bereitgestellte Bézout-Koeffizient immer einen Grad kleiner als d hat . Zweitens kann der größte gemeinsame Teiler, der bereitgestellt wird, wenn die Eingangspolynome teilerfremd sind, beliebige von Null verschiedene Elemente von K sein ; dieser Bézout-Koeffizient (ein Polynom im Allgemeinen positiven Grades) muss also mit der Umkehrung dieses Elements von K multipliziert werden . Im folgenden Pseudocode ist p ein Polynom vom Grad größer als eins und a ist ein Polynom.

function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Beispiel

Wenn beispielsweise das zur Definition des endlichen Körpers GF(2 ⁸ ) verwendete Polynom p = x ⁸  +  x ⁴  +  x ³  +  x  + 1 ist und a = x ⁶  +  x ⁴  +  x  + 1 das Element ist, dessen Inverses erwünscht ist, führt das Ausführen des Algorithmus zu der in der folgenden Tabelle beschriebenen Berechnung. Erinnern wir uns daran, dass in Feldern der Ordnung 2 ⁿ gilt – z = z und z + z = 0 für jedes Element z im Feld). Da 1 das einzige Nicht-Null-Element von GF(2) ist, wird die Anpassung in der letzten Zeile des Pseudocodes nicht benötigt.

Die Umkehrung ist also x ⁷  +  x ⁶  +  x ³  +  x , wie man bestätigen kann, indem man die beiden Elemente miteinander multipliziert und den Rest mit p des Ergebnisses nimmt.

Der Fall von mehr als zwei Zahlen

Man kann den Fall von mehr als zwei Zahlen iterativ behandeln. Zuerst zeigen wir das . Um dies zu beweisen, lassen Sie . Definitionsgemäß ist gcd ein Teiler von und . Also für einige . Ähnlich ist ein Teiler von so für einige . Lassen Sie . Durch unsere Konstruktion von , aber da ist der größte Teiler eine Einheit . Und da ist das Ergebnis bewiesen. ${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c)}$${\displaystyle d=\gcd(a,b,c)}$${\displaystyle d}$${\displaystyle a}$${\displaystyle b}$${\displaystyle \gcd(a,b)=kd}$${\displaystyle k}$${\displaystyle d}$${\displaystyle c}$${\displaystyle c=jd}$${\displaystyle j}$${\displaystyle u=\gcd(k,j)}$${\displaystyle u}$${\displaystyle ud|a,b,c}$${\displaystyle d}$${\displaystyle u}$${\displaystyle ud=\gcd(\gcd(a,b),c)}$

Also , wenn dann gibt es und so , dass so die endgültige Gleichung wird ${\displaystyle na+mb=\gcd(a,b)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}$

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,}$

Um dann auf n Zahlen anzuwenden, verwenden wir Induktion

${\displaystyle \gcd(a_{1},a_{2},\dots,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{ 3},\dots,\gcd(a_{n-1}\,,a_{n}))),\dots),}$

mit den direkt folgenden Gleichungen.

Siehe auch

• Euklidische Domäne
• Linearer Kongruenzsatz
• Kuṭṭaka

Verweise

• Knut, Donald . Die Kunst der Computerprogrammierung . Addison-Wesley. Band 2, Kapitel 4.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest und Clifford Stein . Einführung in Algorithmen , Zweite Auflage. MIT Press und McGraw-Hill, 2001. ISBN  0-262-03293-7 . Seiten 859–861 von Abschnitt 31.2: Größter gemeinsamer Teiler.

Externe Links

• Quelle für die Form des Algorithmus, der verwendet wird, um die multiplikative Inverse in GF(2^8) zu bestimmen