Erweiterter euklidischer Algorithmus

Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler $\operatorname {ggT} (a,b)$ zweier natürlicher Zahlen $a$ und $b$ noch zwei ganze Zahlen $s$ und $t$ die die folgende Gleichung erfüllen

$\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$

Wie der Name schon aussagt ist dieser Algorithmus eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers. Die Erweiterung liefert einen konstruktiven Beweis für das Lemma von Bézout.

Die Darstellung als Linearkombination (selten auch Vielfachsummendarstellung genannt) $\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ liefert das multiplikative Inverse von a modulo b, falls a und b teilerfremd sind, d. h. $ggT(a,b)=1$. In diesem Fall ist s das multiplikative Inverse.

Funktionsweise

Zur Berechnung werden die Variablen m, n, s, t, u und v verwendet. Diese werden wie folgt initialisiert:

• Setze m = a, n = b, s = 1, t = 0, u = 0, v = 1

• Wiederhole solange n ≠ 0

1. Berechne q und r mit m = q * n + r (Division mit Rest)
2. Setze m = n, n = r, u' = s - q * u, v' = t - q * v
3. Setze s = u, t = v, u = u', v = v'

Nach Beendigung ist $\operatorname {ggT} (a,b)=m=s\cdot a+t\cdot b$.

Man kann dieses Vorgehen in der folgenden Form übersichtlich darstellen:

${\begin{matrix}a&=&1\cdot a&+&0\cdot b\\b&=&0\cdot a&+&1\cdot b\\\vdots &&\vdots &&\vdots \\m&=&s\cdot a&+&t\cdot b\\n&=&u\cdot a&+&v\cdot b\\r=m-qn&=&(s-qu)\cdot a&+&(t-qv)\cdot b\end{matrix}}$

Dabei ist q der ganzzahlige Anteil von m/n.

Man zieht also immer von der vorletzten Zeile die mit q multiplizierte letzte Zeile ab, um die nächste Zeile zu erhalten. Wenn die Abbruchbedingung n=0 erfüllt ist, gilt m = r = ggT(a,b) und folglich

$\operatorname {ggT} (a,b)=s\cdot a+t\cdot b.$

Rekursive Variante

Für den erweiterte euklidische Algorithmus existiert auch eine rekursive Variante, die durch den folgenden Pseudocode gegeben ist:

a,b: zwei Zahlen für die der erweiterte euklidische Algorithmus durchgeführt wird

extended_euclid(a,b)
1  wenn b = 0
2      dann return (a,1,0)
3  (d',s',t') $\leftarrow$ extended_euclid(b, a mod b)
4  (d,s,t) $\leftarrow$ (d',y',x' - floor(a/b)y')
5  return (d,s,t)

Beziehung zu Kettenbrüchen

Die Folge der auftretenden Zahlen $q$ liefert die Kettenbruchdarstellung von $a/b$. Z. B. ergibt sich für $a=37$ und $b=16$:

${\begin{matrix}37&=&1\cdot 37&+&0\cdot 16\\16&=&0\cdot 37&+&1\cdot 16;&q=2\\5&=&1\cdot 37&-&2\cdot 16;&q=3\\1&=&(-3)\cdot 37&+&7\cdot 16;&q=5\\0&=&16\cdot 37&-&37\cdot 16\end{matrix}}$

Also ist $\operatorname {ggT} (37,16)=1=(-3)\cdot 37+7\cdot 16$ und

${\frac {37}{16}}=2+{\frac {1}{3+{\frac {1}{5}}}}.$

Quelltext

Unter MATLAB könnte der Algorithmus wie folgt implementiert werden:

function a=eeuklid(a,b)

m=a; n=b;
s=1; t=0;
u=0; v=1;

while n>0
  q=floor(m/n); % Der Quotient wird abgerundet
  r=m-q*n;
  m=n; n=r;
  tmp=u; u=s-q*u; s=tmp;
  tmp=v; v=t-q*v; t=tmp;
end

a=[m,s,t];

Anwendungsbeispiele

• Rabin-Kryptosystem
• RSA-Kryptosystem

Weblinks

Umfangreiche Arbeit u.a. zum euklidischen Algorithmus

Ein kleines Script findet sich unter http://www.mirsky.de/ggt.php. Jeder Schritt wird genau erklärt. Außerdem gibt es noch ein ausführliches Skript mit Quelltext unter [1].