Übung 6

Fakultät für Informatik
Professur Theoretische Informatik
und Informationssicherheit
Wintersemester 2009/10
Prof. Dr. Hanno Lefmann
Datenschutz und Datensicherheit
Ab Übungsblatt 7 wird es die Möglichkeit geben, zur Erbringung einer
Prüfungsvorleistung schriftliche Lösungen der Übungsaufgaben abzugeben. Diese werden dann korrigiert und bewertet.
6. Übung
Aufgabe 1 Zeigen Sie, dass die Anzahl der Iterationen, die der Euklidische Algorithmus für zwei Zahlen r0 , r1 bis zur Terminierung durchführt, höchstens linear in
der Eingabelänge ist.
Hinweis: Startend mit dem Paar (r0 , r1 ) haben wir nach i Iterationen ein aktuelles
Paar (ri , ri+1 ). Zeigen Sie zunächst, dass ri + ri+1 exponentiell mit der Anzahl i an
Iterationen fällt. Als Basis eines Induktionsbeweises kann man zeigen, dass ri +ri+1 ≤
2
· (ri−1 + ri ) ist für alle Iterationen i.
3
Aufgabe 2 Die Fibonacci-Zahlen Fn sind definiert über die Rekursion F0 = 0,
F1 = 1 und Fi = Fi−1 + Fi−2 für i ≥ 2. Zeigen Sie, dass der Euklidische Algorithmus
auf der Eingabe (r0 , r1 ) = (Fn , Fn−1 ) genau n − 1 Iterationen durchführt.
Hinweis: Man kann zeigen, dass der Euklidische Algorithmus die Folge der FibonacciZahlen durchläuft für unsere Eingabe.
Aufgabe 3 Zeigen Sie, dass Fn ≤ 2n ist für alle Fibonacci-Zahlen Fn . Wie kann man
hiermit unter Verwendung des Ergebnisses aus Aufgabe 2 zeigen, dass es Eingaben
gibt, auf denen der Euklidische Algorithmus nicht nur höchstens linear sondern auch
mindestens linear in der Eingabelänge viele Iterationen durchführt?
Aufgabe 4 Sei n = p · q für zwei verschiedene Primzahlen p, q. Zeigen Sie, dass
ϕ(n) = (p−1)(q −1) ist für solche Zahlen. Wir verwenden hier einfach die Definition
von ϕ(n) als Anzahl der Zahlen in {1, . . . , n − 1} die teilerfremd zu n sind.

Download Report