Continued Fraction Algorithm von Wiener

15.06.2012, 17:58	tejubin	Auf diesen Beitrag antworten »
Continued Fraction Algorithm von Wiener Meine Frage: Ich untersuche für meine Bachelor-Arbeit den 'Continued Fraction Algorithm' zur Bestimmung einer Zahl f, wenn man eine untere Abschätzung $\begin{eqnarray} f' = f \cdot (1- \delta), \ \delta \geq 0 \end{eqnarray}$ hat. Man benutzt die reguläre Kettenbruchentwicklung von $\begin{eqnarray} f \end{eqnarray}$ und $\begin{eqnarray} f' \end{eqnarray}$ . $\begin{eqnarray} f = \langle q_0, \ldots, q_m \rangle \end{eqnarray}$ $\begin{eqnarray} f' = \langle q_{0}', \ldots, q_{m}' \rangle \end{eqnarray}$ wobei die Kettenbruchentwicklung so aussschaut: $\begin{eqnarray} f = q_0+\frac{1}{q_1+\frac{1}{q_2+\frac{1}{\quad\stackrel{\vdots}{q_{m-1}+\frac{1}{q_m}}}}} \end{eqnarray}$ Die von $\begin{eqnarray} f' \end{eqnarray}$ analog mit $\begin{eqnarray} q_{k}' \end{eqnarray}$ . Man kann die Zahlen $\begin{eqnarray} f = \frac{n_m}{d_m} \end{eqnarray}$ aus ihrer Kettenbruchdarstellung auch wie folgt rekonstruieren: $\begin{eqnarray} n_0 = q_0, d_0 = 1\\<br /> n_1 = q_0 \cdot q_1 + 1, d_1 = q_1\\<br /> n_i = q_i \cdot n_{i-1} + n_{i-2}\\<br /> d_i = q_i \cdot d_{i-1} + d_{i-2}<br /> \end{eqnarray}$ Der eigentliche Algorithmus lautet nun wie folgt: Wiederhole die folgenden Schritte bis f gefunden ist: - Bestimme/Generiere $\begin{eqnarray} (q_{i}') \end{eqnarray}$ aus der Kettenbruchentwicklung von $\begin{eqnarray} f' \end{eqnarray}$ . - Benutze den oben beschriebenen Weg, um den Bruch folgender Zahl zu bestimmen: :-: $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}' +1 \rangle \end{eqnarray}$ wenn $\begin{eqnarray} i \end{eqnarray}$ gerade ist :-: $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}'\rangle \end{eqnarray}$ wenn $\begin{eqnarray} i \end{eqnarray}$ ungerade ist - Prüfe, ob der so konstruierte Bruch gleich f ist. Das ist soweit verständlich, da auch erklärt wurde, dass für gerades $\begin{eqnarray} i \end{eqnarray}$ gilt: $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}' +1 \rangle > \langle q_{0}', \ldots, q_{i}' \rangle \end{eqnarray}$ Man versucht sich also dem gesuchten $\begin{eqnarray} f \end{eqnarray}$ von unten zu nähern. Nun zu meinem Problem: Direkt nach der Definition des Algorithmus wird eine Aussage getroffen, wann der Algorithmus erfolgreich ist. Nämlich laut Autor, wenn $\begin{eqnarray} f' \end{eqnarray}$ folgende Bedingung erfüllt: $\begin{eqnarray} (1) \langle q_{0}, \ldots, q_{m} - 1 \rangle < f' \leq \langle q_{0}, \ldots, q_{m} \rangle \text{wenn m gerade}\\<br /> (2) \langle q_{0}, \ldots, q_{m} + 1 \rangle < f' \leq \langle q_{0}, \ldots, q_{m} \rangle \text{wenn m ungerade} \end{eqnarray}$ Mir ist allerdings nicht so klar, warum das gelten sollte. Meine Ideen: Naja, ich habe mir überlegt, dass die Behauptung ja quasi aussagt, dass in einem Iterationsschritt (oder insgesamt?) des Algorithmus keine größere 'Entfernung' zurückgelegt werden kann, als eben die Differenz der $\begin{eqnarray} f' \end{eqnarray}$ umspannenden Zahlen in der Ungleichung $\begin{eqnarray} (1) \end{eqnarray}$ . Hierfür habe ich mir den Algorithmus in PARI programmiert, um ein wenig Gefühl für den Ablauf zu bekommen. Die getroffene Behauptung/Aussage scheint richtig zu sein. Habe mir dann versucht klar zu machen, was der Schritt von $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}' \rangle \end{eqnarray}$ zu $\begin{eqnarray} \langle q_{0}', \ldots, q_{i} +1' \rangle \end{eqnarray}$ wenn $\begin{eqnarray} i \end{eqnarray}$ gerade ist, auswirkt. Wiederum ein wenig herumgespielt und dann ist mir folgendes aufgefallen: Es scheint so, als würde die Differenz bei geradem $\begin{eqnarray} i \end{eqnarray}$ einer Regel folgen: $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}' +1 \rangle - \langle q_{0}', \ldots, q_{i}' \rangle = \frac{1}{d_{i}' \cdot d_{i}^{+1}} \end{eqnarray}$ Wobei $\begin{eqnarray} d_{i}' \end{eqnarray}$ der Nenner der Bruchdarstellung von $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}'\rangle \end{eqnarray}$ und $\begin{eqnarray} d_{i}^{+1} \end{eqnarray}$ der von $\begin{eqnarray} \langle q_{0}', \ldots, q_{i}' +1\rangle \end{eqnarray}$ ist. Diese habe ich dann auch bewiesen. Nur weiß ich nicht, inwiefern mich das jetzt weiter bringt. Es wäre super, wenn mir das jemand auf die Sprünge helfen würde, ich möchte einfach nur nachvollziehen können, warum der Algorithmus genau dann erfolgreich ist, wenn [latex]f'[latex] die oben aufgestellte Bedingung erfüllt.
17.06.2012, 12:46	tejubin	Auf diesen Beitrag antworten »
Hier nochmal die Arbeit, auf die ich mich beziehe: http://madchat.awired.net/crypto/codebre...etExponents.pdf Seite 4 und 5 sind die wichtigen, wäre echt toll, wenn mir da jemand hekfen könnte!
20.06.2012, 23:14	Abakus	Auf diesen Beitrag antworten »
Hallo, interessantes Thema. Ich denke, es bietet sich an, diese Attacke einmal zu programmieren und einfach auszuprobieren, PARI sagt mir gerade nichts, aber prinzipiell lassen sich ja alle Zwischenergebnisse anzeigen. Lässt sich daraus schlauer werden? Abakus
24.06.2012, 21:43	tejubin	Auf diesen Beitrag antworten »
Programmiert habe ich den Algorithmus bereits. Die Aussage scheint zu stimmen. Meine Idee ist noch: Im Algorithmus werden die ersten $\begin{eqnarray} i \end{eqnarray}$ Teilnenner von $\begin{eqnarray} f' \end{eqnarray}$ genommen, letzter um einen erhöht und geprüft, ob der so generierte Bruch gleich $\begin{eqnarray} f \end{eqnarray}$ ist. Also müssen die ersten $\begin{eqnarray} n-1 \end{eqnarray}$ Teilnenner von $\begin{eqnarray} f \end{eqnarray}$ und $\begin{eqnarray} f' \end{eqnarray}$ übereinstimmen, damit mit Schritt zwei aus dem Algorithmus $\begin{eqnarray} f \end{eqnarray}$ generiert wird. Was anderes scheint die Aussage nicht auszudrücken.
24.06.2012, 21:57	Abakus	Auf diesen Beitrag antworten »
Ich bin jetzt nicht so in dem Thema drin, dass ich da exakt durchschaue, obwohl ich es auch mal programmieren müsste eigentlich. Vielleicht hilft dir eine kurze Darstellung von Dan Boneh weiter: Twenty Years on Attacks on RSA... (googeln!) Abakus
24.06.2012, 22:36	tejubin	Auf diesen Beitrag antworten »
Das von dir zitierte Paper habe ich bereits gelesen. Es zitiert höchstens aus Wiener. Ich denke meine Überlegungen sollten stimmen!
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »