GCD-Algorithmen

4.1 GCD-Algorithmen

4.1.1 EUKLID’s Algorithmus

Der Algorithmus von EUKLID berechnet den größten gemeinsamen Teiler $d = gcd(a,b)$ zweier natürlicher Zahlen $a,b∈ ℕ$ . Die grundlegende, iterativ angewendete Rechenoperation dabei ist modulare Division.³⁶ Algorithmus 1 beschreibt das klassische Verfahren [Knu98, Sho05, CP05, MvV92, Ber84]. Es beginnt unter der Voraussetzung $a > b$ mit einer Modulo-Division $c2 = a mod b$ . Im nächsten Schritt wird $c2$ als Modul verwendet und $c3 = b mod c2$ berechnet, wonach $c4 = c2 mod c3$ folgt usw. . Diese (wegen $ck+1 < ck$ ) absteigende Sequenz endet wenn $ck+1 = 0$ wird³⁷ – das Ergebnis $d$ befindet sich dann in $ck$ .

Algorithmus 1: Euklidischer Algorithmus $d = gcd(a,b)$

Require: $a ≥ b$ $c ⇐ a 0$ , $c ⇐ b 1$
$k ⇐ 0$
repeat
$k ⇐ k + 1$
$ck+1 ⇐ ck−1 mod ck$
until $ck+1 = 0$
$gcd(a,b) ⇐ ck$

Beweis Jeder Iterationsschritt $ci+1 = ci−1 mod ci$ kann in der Umkehrung (vgl. Restklassenbeziehung 3.2 in Abschnitt 3) als

ci−1 = qi+1ci+ci+1, 0≤ ci+1 < ci

geschrieben werden. So gesehen wird durch den Algorithmus der folgende Abstieg vorgenommen:

bis $ck+1$ verschwindet.

Warum $d = ck$ ein gemeinsamer Faktor von $a$ und $b$ ist, wird klar wenn man die Folge rückwärts betrachtet. In der letzten Zeile steht $ck−1 = qk+1d$ , also teilt $d$ den Rest $ck−1$ (oder kürzer $d |ck−1$ ). Wenn $d$ aber als Faktor in $ck−1$ enthalten ist, dann kann man $d$ auf der rechten Seite der vorletzten Gleichung ausklammern, weshalb es auch als Faktor in $ck−2$ vorkommen muß. Dies setzt sich bis in die erste Gleichung fort (sämtliche Divisionsreste $c0,c1,...,ck$ enthalten folglich $d$ als Teiler), in der die Startbedingung $c = a 0$ und $c = b 1$ verankert ist. Deshalb ist der gemeinsame Teiler $d$ sowohl in $a$ als auch $b$ enthalten.

Viel kürzer kann man damit argumentieren, daß die Modulo-Division $c = c mod c i+1 i−1 i$ eine GCD erhaltende Operation ist. Denn mit der Zerlegung $- ci = cid$ gilt ausgehend von Formel 3.2:

d. h. der gemeinsame Teiler $d$ in $ci−1$ und $ci$ ist auch in $ci+1$ wieder enthalten.³⁸

gcd (ci−1,ci)= gcd(ci+1,ci)= gcd(ci−1 mod ci,ci)

(4.2)

Damit $d$ wirklich den größten gemeinsamen Teiler stellt, muß es überhaupt alle gemeinsamen Teiler enthalten. Mit dem Ziel dies nachzuweisen betrachten wir nochmals die Folge beginnend mit der vorletzten Gleichung, welche nach $c = d k$ umgestellt wird. Ersetzt man darin $c k−1$ mit Hilfe der vorvorletzten Gleichung und fährt aufsteigend fort, so erhält man eine lineare Darstellung für $d = gcd(a,b)$ ,

welche auf ganzen Zahlen $α,β ∈ ℤ$ sowie $c0 = a$ und $c1 = b$ beruht.

Mit Hilfe von Formel 4.3, welche auch Satz von BéZOUT genannt wird,³⁹ kann jetzt relativ einfach bewiesen werden, daß $d$ wirklich der größte gemeinsame Teiler ist. Nehmen wir dazu an, es gäbe einen weiteren gemeinsamen Teiler $′ d$ . Dann würde dieser (auf der rechten Seite von Gleichung 4.3) als Faktor von $a$ und $b$ auszuklammern sein und deshalb (wenn man die linke Seite betrachtet) als Teiler von $d$ auftreten. Mit anderen Worten stecken alle weiteren Teiler (schon) in $d$ , weshalb nur dieser der größte gemeinsame Teiler sein kann.

Hinweis Es existieren unendlich viele lineare Darstellungen für $d$ als Linearkombination von $a$ und $b$ (vgl. auch die kurze Betrachtung zu diophantischen Gleichungen auf Seite 117). Jede Substitution der Art $α := α + nb-$ und $β := β − na-$ , mit

erfüllt BéZOUT’s Identität 4.3 ebenso.

Die kleinsten Werte für $|α|$ und $|β|$ zeichnen sich folglich durch die Relationen $-- |α |< b$ und $-- |β|< a$ aus. Um sie zu ermitteln kann man entweder $-- a$ und $-- b$ sukzessive von $α$ und $β$ subtrahieren/addieren oder man reduziert die BéZOUT-Kofaktoren mit Hilfe von $⌊ -⌋ q = |α|∕b$ bzw. $-- q= ⌊|β|∕a⌋$ und folgender Formeln:⁴⁰

4.1.2 Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus erlaubt eine effiziente Berechnung der BéZOUT-Kofaktoren $α$ und $β$ zusammen (und gleichzeitig) mit dem größten gemeinsamen Teiler (siehe auch [Knu98, Sho05, CP05, Ber84]). Dazu berücksichtigt er einige Erkenntnisse aus dem vorigen Abschnitt, insbesondere daß:

der größte gemeinsame Teiler $d = gcd(a,b)$ für $α,β ∈ ℤ$ als Linearkombination $αa + β b$ darstellbar ist;
$d$ für $0≤ i≤ k$ jeden Rest $ci$ teilt und damit die Darstellung $- ci = dci = αia+ βib$ rechtfertigt;
die Berechnung von $ci+1$ mit Hilfe von $qi+1 = ⌊ci−1∕ci⌋$ und $ci+1 = ci−1− qi+1ci$ erfolgen kann.

Durch Induktion ergibt sich aus

- ci = ci−2− qici−1 = dci = αia+ βib

(4.5)

wenn man $ci−1 = αi−1a+ βi−1b$ und $ci = αia+ βib$ berücksichtigt:

Vergleich mit Ausgangsformel 4.5 erlaubt die Bestimmung von $αi+1$ und $βi+1$ .

Mit den Startwerten $α0 = 1$ und $β0 = 0$ (gewährleistet $c0 = a$ ) bzw. $α1 = 0$ und $β1 = 1$ (ebenso für $c1 = b$ ) kann man den erweiterten euklidischen Algorithmus 2 formulieren.

Algorithmus 2: Erweiterter euklidischer Algorithmus

Require: $a ≥ b$ $(c ,α ,β )⇐ (a,1,0) 0 0 0$
$(c1,α1,β1)⇐ (b,0,1)$
$k ⇐ 0$
repeat
$k ⇐ k + 1$
$q ⇐ ⌊ck−1∕ck⌋$ {Integer-Division}
$(ck+1,αk+1,βk+1) ⇐ (ck−1,αk−1,βk−1)− q(ck,αk,βk)$ { $ck+1 = ck−1 mod ck$ }
until $ck+1 = 0$
$(d,α,β )⇐ (c ,α ,β ) k k k$

Er endet ganz genauso wie Algorithmus 1 bei $ck+1 = 0$ , ermittelt aber zusätzlich die BéZOUT-Kofaktoren $α = αk$ und $β = βk$ sowie die teilerfremden Anteile $a= a∕d$ und $-- b= b∕d$ . Letztere findet man wegen $ck+1 = αk+1a + βk+1b= 0$ am Ende in $βk+1$ und $αk+1$ . Dies wird relativ schnell aus

ersichtlich, wenn man auf beiden Seiten der letzten Gleichung das kleinste gemeinsame Vielfache anvisiert.

Hinweis Als Ergänzung zum Hinweis von Seite 77 kann man sogar feststellen, daß die „Wahl“ von $q$ nicht unbedingt mit einer Modulo-Division verbunden sein muß. Etwas anders könnte man $q$ einfach so wählen, daß

die Folge der $ck$ weiterhin eine absteigende Sequenz ist;
und in jedem Iterationsschritt $qc ≤ c k k− 1$ gilt (wodurch $c ≥ 0 k+1$ gewährleistet ist).

Den steilsten Abstieg $Δ = ck+1 − ck$ erreicht man allerdings, wenn $q$ im jeweiligen Iterationsschritt maximal ist. Dies ist aber unter der Voraussetzung $ck+1 ≥ 0$ genau bei einer Modulo-Division $ck+1 = ck−1 mod ck$ der Fall. Ansonsten ist jeder Wert $q= 0 ...⌊ci− 1∕ci⌋$ geeignet — einzig die Konvergenzgeschwindigkeit nimmt mit kleineren Werten von $q$ ab.⁴¹

4.1.3 EUKLID’s Algorithmus für Polynome über $ℤ2$

Für Polynome mit Koeffizienten aus $GF (2)$ kann man ganz ähnlich verfahren [HMV04, 2.3.6],[Sho05, 17.3], [CP05, 2.2.1], [Ber84, 2.1]. Mit Rückblick auf den Hinweis von Seite 83 muß man nur folgendes beachten:

Addition und Subtraktion sind gleichwertig (und die Addition wird zu einem Exklusiv-Oder $⊕$ ).
An die Stelle eines wertbehafteten Vergleichs $ck−1 ≥ ck$ tritt ein Vergleich des Polynomgrades $degc ≥ degc k−1 k$ .
Die Vorbedingung $deg a≥ degb$ kann entfallen, da der Algorithmus selbst die Vertauschung der Argumente vornimmt.
Die Ermittlung von läßt sich in folgende Einzelfälle zerlegen:
- $degck−1(x)< degck(x)$ führt zu $q(x)= 0$ , was nach Algorithmus 3 einer Vertauschung $(ck,αk,βk)⇐ ⇒ (ck−1,αk−1,βk−1)$ entspricht.
- $degck−1(x)= degck(x)$ ergibt $q(x) = 1$ , was mit $(ck+1,αk+1,βk+1)⇐ (ck− 1,αk−1,βk−1)+ (ck,αk,βk)$ im nachfolgenden Fall aufgeht.
- Für $degck−1(x)> degck(x)$ müßte man $q(x) = ⌊ck− 1(x)∕ck(x)⌋$ berechnen. Mit der Option auch ein kleineres $q(x)$ zu verwenden (siehe Hinweis auf Seite 83), kann man sich eine vollständige Polynomdivision sparen. Stattdessen ist eine sinnvolle Vorgehensweise sich bei der Divison auf das höchstwertige Bit von $ck−1(x)$ und $ck(x)$ beschränken. In einer monischen Polynomrepräsentation (der höchstwertige Koeffizient ist 1) führt die Division so zu: $xdegck−1−degck$ .

Algorithmus 3: Erweiterter euklidischer Algorithmus für Polynome in $ℤ2[x]$

$(c0,α0,β0)⇐ (a,1,0)$
$(c1,α1,β1)⇐ (b,0,1)$
$k ⇐ 0$
repeat
$k ⇐ k + 1$
if $deg ck− 1 ≥ degck$ then
$degck−1−degck q ⇐ x$ { $q(x) = 1$ im Fall: $degck−1(x) = degck(x)$ }
else
$q ⇐ 0$ {führt letztlich zu: $(ck+1,αk+1,βk+1 )⇐ (ck−1,αk−1,βk− 1)$ }
end if
$(ck+1,αk+1,βk+1) ⇐ (ck−1,αk−1,βk−1)⊕ q(ck,αk,βk)$
until $ck+1 = 0$
$(d,α,β )⇐ (c ,α ,β ) k k k$

4.1.4 Binärer GCD-Algorithmus

Der binäre GCD-Algorithmus kommt im Gegensatz zum klassischen euklidischen Algorithmus ohne Divisionen aus [CP05, Knu98, Ste67, Wel01]. Statt dessen wird (beginnend mit $a0 = a$ und $b = b 0$ ) durch Subtraktion und Halbierung eine stetige Reduktion der Argumente $a$ und $b$ vorgenommen, welche letztlich zum größten gemeinsamen Teiler $d = gcd(a,b)$ führt.⁴²

Der Algorithmus endet spätestens dann, wenn im Schritt $i= k$ eines der beiden Argumente $ai$ oder $bi$ verschwindet (im obigen Fall beispielhaft für $bk = 0$ ). Das Reduktionsschema zeigt Tabelle 4.1.

Tabelle 4.1: Reduktionsschema des binären GCD-Algorithmus


$ai$	$bi$	$gcd(ai+1,bi+1)=$	Begründung


gerade		$( ) 2gcd ai,bi 2 2$	gemeinsamer Teiler ist 2

gerade	ungerade	$( ai ) gcd 2 ,bi$	2 ist kein gemeinsamer Teiler

ungerade	gerade	$( ) bi gcd ai,2$	2 ist kein gemeinsamer Teiler

ungerade, $a ≥ b i i$		$( ) gcd ai−-bi,b 2 i$	$a − b i i$ , wie auch $ai+ bi$ , enthalten den Teiler $gcd(a ,b )= d i i$ , denn $-- ai = aid$ , $-- bi = bid$ führt zu $-- -- gcd(ai− bi,bi)= gcd[d(ai− bi),bid]$ . Außerdem sind sowohl Summe als auch Differenz gerade Zahlen ( $ai = 2ν+ 1$ , $bi = 2μ + 1$ ergibt $ai− bi = 2(ν− μ )$ ), weshalb 2 als gemeinsamer Teiler wieder ausgeschlossen werden kann.

ungerade, $bi ≥ ai$		$gcd(ai,bi−2ai)$	siehe Fall $ai > bi$

$ai > 0$	$0$	$ai$	$ai$ ist größter gemeinsamer Teiler mit $0$

$0$	$b > 0 i$	$b i$	$b i$ ist größter gemeinsamer Teiler mit $0$

Anmerkungen

Bezüglich gibt es genau eine Situation, die das Verschwinden von hervorruft (genauso bezüglich und ) . Betrachtet man dazu Tabelle 4.1, so wird in folgenden Fällen reduziert:
1. $ak−1$ und $bk−1$ sind gerade: Halbierung von $ak−1 = 1$ ergibt $0$ , bedeutet aber ungerades $ak−1$ (Widerspruch).
2. $ak−1$ gerade, $bk−1$ ungerade: Halbierung von $ak− 1 = 1$ ergibt $0$ , was ebenfalls ungerades $a k−1$ bedeutet (Widerspruch).
3. $ak−1$ und $bk−1$ sind ungerade: Halbierung von $bk−1− ak−1 = 1$ ergibt $0$ , aber unter der Voraussetzung $bk−1 = ak−1 + 1$ können niemals beide ungerade sein (Widerspruch).
4. $ak−1$ und $bk−1$ sind ungerade: Halbierung von $bk−1 = ak−1$ führt zu $ak = 0$ und stellt damit den einzig möglichen Fall im Schritt $k− 1$ dar.
In jedem Iterationszyklus wird entweder $ai$ oder $bi$ um mindestens ein Bit reduziert.⁴³ Aus diesem Umstand läßt sich (im Fall $a0 > b0$ ) für die Anzahl der Iterationsschritte $⌈log2a0⌉ ≤ k≤ 2 ⌈log2a0⌉$ schlußfolgern (vgl. auch [Kal95, Theorem 2]).
Die Halbierung des Arguments für den Fall, daß $ai$ und $bi$ ungerade sind, muß man nicht unbedingt im Iterationsschritt $i$ ausführen. Es ist durchaus legitim, falls beispielsweise $a ≥ b i i$ gilt, einfach nur $ai+1 = ai− bi$ zu berechnen. Die Differenz ergibt ja bekanntlich wieder eine gerade Zahl (dann ist $ai+1$ gerade, $bi+1$ ungerade) und es kommt im nächsten Iterationsschritt zu der gewünschten Halbierung.
Den Fall, daß sowohl $ai$ als auch $bi$ gerade sind, kann man grundsätzlich aus der Haupt-Iterationsschleife herausziehen. Denn wird einmal eines der beiden Argumente ungerade, dann kann dieser Fall niemals wieder eintreten (genau das ungerade Argument ist in allen anderen Reduktionsfällen unveränderlich). Solange beide Argumente gerade sind, kann man sie also kontinuierlich reduzieren, bis nach $n$ Schritten entweder $ai$ oder $bi$ ungerade geworden ist. Danach kann auf $an = a ∕2n$ und $bn = b∕2n$ irgendein binärer (erweiterter) GCD-Algorithmus angewendet werden, der $gcd(a,b )= α a + β b n n n n n n$ ermittelt.

Der so ermittelte größte gemeinsame Teiler muß am Schluß nur noch mit $2n$ multipliziert werden (also um $n$ Bit verschoben), was auch Algorithmus 4 entsprechend wiedergibt.⁴⁴ Wir können deshalb in den Betrachtungen zum erweiterten binären GCD-Algorithmus (siehe nächste Abschnitte) immer voraussetzen, daß $a$ oder $b$ ungerade ist.

Algorithmus 4: Reduktion gerader Argumente

$n ⇐ 0$
while $a$ gerade $∧$ $b$ gerade do
$a ⇐ a ∕2$
$b ⇐ b ∕2$
$n ⇐ n + 1$
end while
$d ⇐ 2n gcd(a,b)$ {GCD-Algorithmus mit Voraussetzung: $a$ oder $b$ ungerade}
Für den Fall, daß entweder oder ungerade ist (oder beide), kann man ausgehend von und feststellen:⁴⁵
- Der größte gemeinsame Teiler $d$ ist ungerade.
- Sollte $a$ ungerade sein, dann ist es dessen teilerfremde Anteil $-- a$ ebenfalls.
- Sollte $b$ ungerade sein, dann ist es dessen teilerfremde Anteil $b-$ auch.

4.1.5 Erweiterter binärer GCD-Algorithmus

Algorithmus nach KALISKI⁴⁶ [Kal95] Betrachtet man das Reduktionsschema des binären GCD-Algorithmus, so kann man verschiedenste lineare Transformationen der Art

definieren, wobei sich die einzelnen Betrachtungsweisen durch unterschiedliche Werte in den Koeffizienten unterscheiden. Bei jedem Schritt sind so $a i$ und $b i$ als lineare Funktion von $a i+1$ und $bi+1$ darstellbar, die Ausgangsgrößen $a0$ und $b0$ deshalb als lineare Funktionen von $ai$ und $bi$ .

Durch Einsetzen von $ai$ und $bi$ in folgende Gleichung,

gefolgt von einem Koeffizientenvergleich, kann man für die konkreten Reduktionsfälle die jeweilige Transformationen der Linearfaktoren ableiten (siehe Tabelle 4.2). Am Beispiel $ai+1 = (ai− bi)∕2$ , $bi+1 = bi$ soll das Vorgehen exemplarisch verdeutlicht werden.

Aus den Transformationen nach Tabelle 4.2 kann man außerdem die Determinante

| | || ui vi || Di = uiti− sivi = | si ti | , mit D0 = 1

bestimmen.

Tabelle 4.2: Linearfaktoren beim binären GCD-Algorithmus nach KALISKI


$ai$	$bi$	$ai+1 =$	$bi+1 =$	$ui+1 =$	$vi+1 =$	$si+1 =$	$ti+1 =$	$Di+1 =$


gerade		$ai 2$	$bi 2$	$2u i$	$2v i$	$2s i$	$2t i$	$4D i$

gerade	ungerade	$a -i 2$	$bi$	$2ui$	$vi$	$2si$	$ti$	$2D i$

ungerade	gerade	$ai$	$bi -- 2$	$ui$	$2vi$	$si$	$2ti$	$2D i$

ungerade, $ai ≥ bi$		$ai− bi --2---$	$bi$	$2ui$	$ui+ vi$	$2si$	$si+ ti$	$2D i$

ungerade, $bi ≥ ai$		$ai$	$bi−-ai 2$	$ui+ vi$	$2vi$	$si+ ti$	$2ti$	$2D i$

Um den Zusammenhang mit den BéZOUT-Koeffizienten $α, β ∈ ℤ$ in $gcd(a,b) = αa0+ β b0$ herzustellen, stellen wir die Formeln 4.6 und 4.7 nach $ai$ und $bi$ um. Dazu werden beide Gleichungen mit den Linearfaktoren der jeweils anderen multipliziert und dann wechselweise voneinander subtrahiert.

Schließt man den Fall aus, daß $a 0$ und $b 0$ gerade sind ( $D = 2i i$ , vgl. Anmerkungen auf Seite 92), dann kann für den letzten Iterationsschritt $i= k$ , in Abhängigkeit davon ob $ak$ oder $bk$ zuerst verschwindet, folgendermaßen konkretisiert werden:

An diesem Punkt stellen wir jedoch fest, daß es sich bei den Größen $uk$ , $vk$ , $sk$ und $tk$ nicht um die Kofaktoren von $gcd(a,b)$ , sondern um eine Linearfaktordarstellung von $2kgcd(a,b)$ handelt.⁴⁷

Um aus $tk$ , $vk$ und $sk$ , $uk$ die BéZOUT-Koeffizienten $α$ und $β$ zu bestimmen, sind zusätzliche Korrekturschritte nötig, welche in [Kal95] auch Korrekturphase (oder Phase II) genannt werden. Ziel ist es dabei, die rechte Seite der letzten Gleichung durch $2k$ zu dividieren (oder in $k$ Schritten wiederholt durch 2). Da die linke Seite immer eine gerade Zahl ist, können folgende Schlußfolgerungen im Falle $b = 0 k$ gezogen werden (falls $a = 0 k$ war, äquivalent für $t → s k k$ und $vk → uk$ ):⁴⁸

Sind $v$ und $t$ gerade, dann ist eine ganzzahlige Halbierung $v := v(g)∕2$ , $t := t(g)∕2$ möglich (d. h. führt wieder zu einer ganzen Zahl).
In allen anderen Fällen ( bzw. ungerade) kann man wegen $i 2 gcd(a,b) = ta − vb= (t+ b)a− (v+ a)b$

die Reduktion $t := (t+ b)∕2$ bzw. $v:= (v+ a)∕2$ vornehmen, ohne daß sich die Gleichung ändert. Man wandelt jedoch die ungerade Zahl $t$ bzw. $v$ in eine gerade Zahl, die dann (wie gewünscht) durch $2$ teilbar ist. Die Ursache liegt einerseits darin begründet, daß die linke (und demzufolge auch rechte) Seite der Gleichung
$2igcd(a,b) = ta − vb$

immer eine gerade Zahl repräsentiert und andererseits, entweder $a$ oder/und $b$ als ungerade vorausgesetzt wurden. Berücksichtigt man die folgenden Gesetzmäßigkeiten:
1. die Summe zweier ungerader oder zweier gerader Zahlen ist eine gerade Zahl;
2. die Summe einer ungeraden und einer geraden Zahl ist eine ungerade Zahl;
3. das Produkt zweier ungerader Zahlen ist eine ungerade Zahl;
4. alle anderen Kombinationen ergeben bei der Multiplikation eine gerade Zahl;
dann sind genau drei Fälle konstruierbar, in denen $t$ oder $v$ ungerade ist.

In allen diesen Varianten führt aber die Addition $t+ b$ bzw. $v+ a$ zu einer geraden Zahl, womit sich das Korrekturverfahren bestätigt.

Algorithmus 5: Algorithmus $d = gcd(a,b) = αa + βb$ nach KALISKI

Require: $a$ ungerade $∨$ $b$ ungerade {Phase I} $(a0,u0,s0) ⇐ (a,1,0)$
$(b0,v0,t0)⇐ (b,0,1)$
$f ⇐ 0$ {Flag, daß anzeigt, ob schlußendlich $α$ oder $β$ negativ ist}
$k ⇐ 0$
while $ak > 0$ do
if $bk > ak$ then
$(bk,vk,tk)⇐ ⇒ (ak,uk,sk)$ {gewährleistet $ak ≥ bk$ }
$-- f ⇐ f$ {invertiere Flag}
end if
if $ak$ ungerade $∧$ $bk$ ungerade then
$(ak,vk,tk)⇐= (ak− bk,vk+ uk,tk +sk)$ { $ak$ ist jetzt gerade, $bk$ weiterhin ungerade}
end if
if $ak$ gerade then
$(ak+1,uk+1,sk+1)⇐= (ak∕2,2uk,2sk)$ { $ak$ gerade, $bk$ ungerade}
else
$(b ,v ,t )⇐= (b∕2,2v ,2t) k+1 k+1 k+1 k k k$ { $a k$ ungerade, $b k$ gerade}
end if
$k ⇐ k + 1$
end while
$gcd(a,b) ⇐ b k$ {Teilergebnis $d = gcd(a,b)$ } {Phase II}
$i⇐ k$
while $i> 0$ do
if $s k$ ungerade $∨$ $u k$ ungerade then
$sk ⇐= sk+ tk$ {Addition von $-- tk = b$ (vgl. Bemerkung 3)}
$u ⇐= u + v k k k$ {Addition von $v = a- k$ (vgl. Bemerkung 3)}
end if
$sk ⇐= sk∕2$ {Korrektur $α$ }
$uk ⇐= uk∕2$ {Korrektur $β$ }
$i⇐ i− 1$
end while
$(α,β )⇐= (sk,uk)$ {Wenn $f = 0$ , dann $α < 0$ , sonst $β$ }

Als Ergebnis kann man Algorithmus 5 formulieren, wobei außerdem folgende Anmerkungen berücksichtigt wurden:

Aus den Gleichungen 4.6 und 4.7 läßt sich im letzten Iterationsschritt (von Phase I)

schlußfolgern, d. h. bei $uk$ und $sk$ handelt es sich im Fall $bk = 0$ (gleichermaßen für $vk$ , $tk$ im Fall $ak = 0$ ) um die teilerfremden Faktoren
Wegen der stetigen Reduktion von $ai$ oder $bi$ müssen die Linearfaktoren $ui$ , $si$ , $vi$ und $ti$ in Phase I schrittweise anwachsen, denn nur so können $a0$ und $b0$ nach Gleichung 4.6 und 4.7 konstant bleiben. In [Kal95, Theorem 1] wird bewiesen, daß keine dieser Größen während der Ausführung des Algorithmus den Maximalwert $2a0− 1$ überschreitet (für $a0 > b0$ ).⁴⁹
Die in Phase II vorzunehmende Addition von $a$ bzw. $b$ kann (entsprechend Anmerkung 5 auf Seite 94) ersetzt werden durch eine Addition von $-- a0$ bzw. $-- b0$ .⁵⁰

Algorithmus nach PENK [Knu98, Exercise 4.5.2.39], [MvV92, 14.4.3] Dieser Algorithmus stellt $ai+1$ und $bi+1$ als lineare Funktion von $ai$ und $bi$ dar, letztlich wird also von $(a0,b0)$ auf $(ai,bi)$ geschlossen.

Vorteilhaft wirkt sich aus, daß im letzten Reduktionsschritt (wenn $ak$ oder $bk$ verschwindet) $uk$ und $vk$ bzw. $sk$ und $tk$ direkt die gesuchten BéZOUT-Kofaktoren $α$ , $β$ darstellen.

Durch Einsetzen von $ai+1$ und $bi+1$ (entsprechend Tabelle 4.1) in die Gleichungen

kann man für den jeweiligen Reduktionsfall die zugehörige Transformationen der Linearfaktoren ableiten. Wieder am Beispiel $ai+1 = (ai− bi)∕2$ , $bi+1 = bi$ soll das Vorgehen veranschaulicht werden ( $ai$ und $bi$ sind ungerade, $ai ≥ bi$ ).

Vergleich von linker und rechter Seite läßt den Schluß zu:

Die anderen Kombinationen können genau nach demselben Schema abgeleitet werden. Tabelle 4.3 faßt die Ergebnisse in übersichtlicher Form zusammen.⁵¹

Tabelle 4.3: Linearfaktoren beim Algorithmus nach PENK


$ai$	$bi$	$ai+1 =$	$bi+1 =$	$ui+1 =$	$vi+1 =$	$si+1 =$	$ti+1 =$


gerade	ungerade	$ai 2$	$bi$	$ui 2$	$vi 2$	$si$	$ti$

ungerade	gerade	$ai$	$b -i 2$	$ui$	$vi$	$s -i 2$	$t -i 2$

ungerade, $ai ≥ bi$		$ai− bi ------ 2$	$bi$	$ui− si ------ 2$	$vi− ti ----- 2$	$si$	$ti$

ungerade, $bi ≥ ai$		$ai$	$bi− ai --2---$	$ui$	$vi$	$si− ui --2---$	$ti− vi -2---$

Dabei tritt allerdings wieder das bekannte Problem auf: Wie kann man die Ganzzahligkeit des jeweiligen Linearfaktoren bei der Halbierung wahren? Die Antwort haben wir schon beim vorangegangenen Algorithmus geliefert – indem die Ausgangsgleichungen 4.8 und 4.9 folgendermaßen erweitert:

und dadurch ungerade Zahlen $ui$ , $vi$ bzw. $si$ , $ti$ in gerade umwandelt.

Beschränken wir uns auf die Kombinationen nach Tabelle 4.3, in denen $ui$ und $vi$ verändert werden (äquivalent für $ui → si$ und $vi → ti$ ). Für den Fall, daß $ai$ gerade und $bi$ ungerade ist (zweite Zeile in 4.3), können wir auf die Argumentation von Seite 100 zurückgreifen (Phase II der Methode nach KALISKI). Sie erlaubt uns die Subtraktion/Addition von $a0$ und $b0$ für den Fall, daß $ui$ oder $vi$ ungerade ist. Die Situation, daß $ai$ und $bi$ ungerade sind (vorletzte Zeile in 4.3), kann man durch gedankliche Verzögerung der Halbierung in den nächsten Iterationsschritt erklären. Wählt man als modifizierten Einzelschritt $a = a − b i+1 i i$ (und entsprechend $u = u − s i+1 i i$ , $v = v − t i+1 i i$ ), so reduziert sich die Fragestellung wieder auf eine gerade Zahl $ai+1 = ui+1a0 +vi+1b0$ , also auf den vorangegangenen Fall.

Als Ergebnis der Ausführungen kann man Algorithmus 6 formulieren. Der Vorteil des Algorithmus (gegenüber KALISKI’s) liegt vor allem darin, daß keine Korrekturphase nötig ist. Nachteilig für eine praktische Umsetzung ist die notwendige Vorzeichen-Arithmetik.

Algorithmus 6: Algorithmus $d = gcd(a,b) = αa + βb$ nach PENK

Require: $b$ ungerade $(a ,u ,v) ⇐ (a,1,0) 0 0 0$
$(b0,s0,t0)⇐ (b,0,1)$
$i⇐ 0$
while $ai > 0$ do
if $b > a i i$ then
$(bi,si,ti)⇐ ⇒ (ai,ui,vi)$ {gewährleistet $ai ≥ bi$ }
end if
if $ai$ ungerade $∧$ $bi$ ungerade then
$(ai,ui,vi) ⇐= (ai− bi,ui− si,vi− ti)$ { $ai$ ist jetzt gerade, $bi$ weiterhin ungerade}
end if
if $ai$ gerade then
$ai+1 ⇐= ai∕2$ { $ai$ gerade, $bi$ ungerade}
if $ui$ gerade $∧$ $vi$ gerade then
$ui+1 ⇐= ui∕2$
$vi+1 ⇐= vi∕2$
else
$u ⇐= (u + b)∕2 i+1 i$
$vi+1 ⇐= (vi− a)∕2$
end if
else
$bi+1 ⇐= bi∕2$ { $ai$ ungerade, $bi$ gerade}
if $si$ gerade $∧$ $ti$ gerade then
$si+1 ⇐= si∕2$
$ti+1 ⇐= ti∕2$
else
$si+1 ⇐= (si+b )∕2$
$ti+1 ⇐= (ti− a)∕2$
end if
end if
$i⇐ i+ 1$
end while
$(d,α,β )⇐ (b ,s,t) i ii$ { $d = gcd(a,b) = αa +β b$ }