Laufzeit des Euklidischen Algorithmus

Question

Hi, komme bei dieser Aufgabe leider absolut nicht weiter, hat jemand eine Idee dazu?

Aufgabe:

$$\boxed {Laufzeit\, des\, Euklidischen\, Algorithmus\, n(a,b) \to Laufzeit\, ggT(a,b)\\ a) F_{n+1} \geq (\frac{1+\sqrt{5}}{2})^{n-1}\\ b) a \geq F_{n(a,b)+2}\\ c) Aus\,\, a)\, und\,\, b)\, folgern\, dass\, n(a,b) \in O(log_2(a))}$$
Danke schonmal für jede Hilfe :)

Comments

Kleiner LaTeX-Tipp: Schreibe normalen Text außerhalb von den LaTeX-Blöcken oder benutze

\text{ text }

für Textpassagen. So kann man den Text besser lesen und die Abstände und die Ausrichtung des Textes sind korrekt.

Answer 1

Hallo,

Antworten und Anregungen auf deine Fragen findest du zum Beispiel in Rothe, Jörg. Komplexitätstheorie und Kryptologie: Eine Einführung in Kryptokomplexität. Springer-Verlag, 2008.. (Falls du studierst - dann hat deine Universität oder Fachhochschule mit hoher Wahrscheinlichkeit eine Lizenz für Bücher von Springer und demnach kannst du dir das kostenlos angucken.)

Dort findest du unter anderem auch einen Beweis zu $$F_n\geq c\cdot \alpha^n \qquad\text{ bzw. } \qquad F_{n+3}\geq c\cdot \left(\frac{1+\sqrt{5}}{2}\right)^{n+3}$$ für Konstanten \(c,\alpha\). Die Gedankengänge dazu sollten dir für deinen Beweis in Aufgabe a) und b) helfen.

Es wird weiterhin bewiesen, dass die Zahl \(k\) der rekursiven Aufrufe von \(\texttt{Euklid}(n,m)\) in \(\mathcal{O}(\log_2 n)\) ist. Das könnte dir bei Aufgabe c) helfen.

Die ganze Komplexitätsanalyse des euklidischen Algorithmus wird sehr ausführlich in "Knuth, Donald E. Art of computer programming, volume 2: Seminumerical algorithms. Addison-Wesley Professional, 2014." beschrieben. Dieses Buch ist eine große Empfehlung für detaillierte Algorithmenanalysen.

Hier findest du eine vollständige Komplexitätsanalyse des Algorithmus.

Grüße,

\(\textsf{Doesbaddel}\)