Pollard's Rho-Methode < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:50 Di 01.11.2011 | | Autor: | julsch |
| Aufgabe | In Pollard's Rho-Methode habe das Anfangsstück Länge i und der Kreis Länge j-i. Zeigen Sie, dass sich die beiden Känguruhs (Känguruh 1 springt immer einen Schritt, Känguruh 2 springt 2 Schritte) im Punkt [mm] s_{m}=s_{2m} [/mm] treffen, wobei
m = [mm] (j-i)*[\bruch{i}{j-i}].
[/mm]
[ ] bezeichnet die Gaußklammer. Es ist nützlich die Identität x mod y = x - [mm] y*\{\bruch{i}{j-i}\} [/mm] zu benutzen, wobei { } die untere Gaußklammer bezeichnet (Abrunden). |
Hallo zusammen,
ich hab ein paar Probleme mit der Aufgabe. Ich hab mir überlegt, dass die Känguruhs sich vor i Schritten nicht treffen können, da das erste Känguruh (K1) immer einen Schritt geht und das zweite (K2) immer 2 Schritte springt.
Ich hab nun eine Fallunterscheidung gemacht,
1.Fall: Die Kanguruhs treffen sich im Punkt i, dann wäre ich feritg.
2.Fall: Die Känguruhs treffen sich nicht im Punkt i. Es gilt dann aber, dass K2 weniger als (j-i) Schritte von K1 entfernt ist.
Ich hatte nun mehrere Ansätze, aber irgendwie gingen alle daneben. Ich hab schon ein Problem allgemein zu sagen, in welchem Punkt sich die Kanguruhs nach k Schritten befinden. Ist k<j, so befindet K1 sich ja im Punkt k. K2 ist bis dahin ja 2k Schritte vorangekommen, d.h. ich muss in irgendeiner Form einen Modulo verwenden, der K2 auf dem Kreis laufen lässt. Ich hatte mir überlegt, dass für die Känguruhs gelten könnte
K1 befindet sich nach k Schritten im Punkt [mm] s_{k}=k [/mm] mod(j-i) + i
K2 befindet sich nach k Schritten im Punkt [mm] s_{k}=2k [/mm] mod (j-i) + i
Nur leider komm ich mit dem Ansatz nich weiter.
Ich hatte mir dann mal das Beispiel i=5 und j=13 vorgenommen. Dort treffen sich die Kanuruhs nach 8 Schritten, jedoch würde ich duch meine Formeln rausbekommen
K1: 8 mod8 + 5 = 0+5=5
K2: 16 mod 8 + 5 =0+5=5
Das Stimmt ja nicht mit dem eigentlichen Treffpunkt überein, also muss in meiner Überlegung schon ein Fehler sein.
Kann mir jemand weiterhelfen?
Liebe Grüße
Julsch
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Do 03.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
