Unterabschnitte
Der Euklidische Algortihmus berechnet den ggT mittels rekursiven Aufrufen
1 folgendermaßen:
Hierbei werden alle Faktoren, die nicht Primfaktoren beider Zahlen sind, herausgezogen, bis letztendlich

übrigbleibt.
Der
Worst-Case-Fall des Euklidalgorithmus sind die Fibonaccizahlen. Die Fibonaccizahlen haben die Eigenschaft, daß wenn man den Rest von

bestimmt,

herauskommt, da

. Es müssen somit genau

Schritte durchgeführt werden, um darauf zu kommen, daß der ggT zweier Fibonaccizahlen, die im Wort-Case aufeinander folgen,

ist.
Für Fibonaccizahlen gilt
Wir sehen, daß je größer die Zahlen werden, die Häufigkeit der Fibonaccizahlen logarithmisch abnimmt, da die Größe der Fibonaccizahlen exponentiell steigt. Somit gilt

.
1.Fall:

ist eine Zweierpotenz, etwa
2.Fall:

beliebig: Sei
1. Fall

:
Für

:
Durch Induktion kann man zeigen (ohne Beweis):
Wobei

die harmonsische Reihe ist, für die gilt:
Hiermit läßt sich

nach

bzw.

abschätzen. Somit ist die Laufzeit im Average Case:
Fußnoten
- ... Aufrufen1
- Es gibt auch ein iteratives Verfahren des Euklidischen Algorithmusses.