Lektion Pollard, Kollisionserkennung

Anleitung zum Selbstudium

Folie 1

• löst die Übungsaufgabe vom letzten Mal (x mod 22) ausrechnen
• schauen Sie den Lösungsweg an und überprüfen Sie das Ergebnis x=20 durch Einsetzen in die Originalgleichung 5^x=12 mod 23
• Üben Sie das Verfahren an weiteren Beispielen, z.B. 3^x=28 mod 31.
  • Hier ist zwar keine Pollard-Folge nötig, weil der größte Primfaktor von p-1 die 5 ist
  • dort führt reines Ausprobieren zum Erfolg.
  • Chinesischer Restsatz muss mehrfach angewendet werden, Zwischenergebnisse sind nämlich x mod 2, mod 3 und mod 5.
    • aus x mod 2 und mod 3 erhält man ein Ergebnis mod 6
    • aus x mod 6 und mod 5 erhält man ein Ergebnis mod 30

Folie 2

hier wird das Verfahren skizziert

• die Folge wird als (y,k,l) protokolliert (siehe letzte Lektion)
• Idee: führe die Folge zweimal aus, einmal in einfacher und einmal in doppelter Geschwindigkeit
• also protokollieren wir (y,k,l) als langsame Folge (in grün) und (y2,k2,l2) als schnelle Folge (in blau)
• irgendwann erreichen beide den Kreis - im Kreis rückt die schnelle Folge in jedem Schritt um eins näher an die langsame Folge heran
• wenn n die Anzahl der Elemente im Kreis ist, so hat nach spätestens n Schritten die blaue Folge die grüne Folge "eingeholt" und es gilt y=y2
• wenn nun k2!=k und l2!=l, dann kann x ausgerechnet werden (siehe letzte Lektion)
• Programmieren Sie ! In Ihrer letzten Implementierung fehlte ein Abbruchkriterium, hier ist es: y2=y.

Folie 3

theoretische Betrachtung, nach wievielen Schritten eine Kollision stattfindet

wir betrachten nur die langsame Folge und zwar für eine Grundmenge von q Elementen

• wir fassen die Zahlenfolge als Zufallsexperiment auf
• bei jedem Schritt ergibt sich ein zufälliges y
• man hat gewonnen, wenn das y schon einmal auftauchte
• das ist wie das Ziehen aus einer Menge mit q Bällen (etwa die aus dem Lotto 6 aus 49), und zwar mit Zurücklegen...zieht man einen Ball ein zweites Mal hat man gewonnen
• also ist die Frage, mit welcher Wahrscheinlichkeit bricht die Folge im i-ten Schritt nicht ab
• wenn es schon ein y gibt, dann rechnet man die Folge weiter, das ist der Fall, wenn beim zweiten Zug einer der q-1 anderen Bälle gezogen wird, dies geschieht mit Wahrscheinlichkeit (q-1)/q
• wenn es schon zwei (also verschiedene) y-Werte gibt, dann wird weitergerechnet, wenn der dritte sich von diesen beiden unterscheidet, also mit Wahrscheinlichkeit (q-2)/q usw.

Folie 4

• der Erwartungswert der Laufzeit ergibt sich aus der Betrachtung, dass die Berechnung abbricht, sobald die Wahrscheinlichkeit des Weiterrechnens kleiner ist als die des Abbruchs
• wir schauen nach der Wahrscheinlichkeit, i Schritte zu rechnen
• also 1 Schritt und 2. Schritt und 3. Schritt und ... und i-ter Schritt
• wegen der und Verknüpfung multiplizieren sich die Wahrscheinlichkeiten
• das Ergebnis (Wahrscheinlichkeit des Weiterrechnens) muss < 1/2 sein
• mit einem Rechentrick über Taylorreihe von exp(x) kommt man auf i ungefähr sqrt(q)
• das analoge Zufallsexperiment ist als Geburtstagsparadoxon bekannt, die Wahrscheinlichkeit, dass bei n Personen mindestens zwei am gleichen Tag Geburtstag haben. Es gibt 365 Tage im Jahr also liegt die Antwort in der Gegend von sqrt(365) was ungefähr 19 ist. In der Tat ist ab n=23 Personen diese Grenze erreicht.

Folie 5

Programmieren Sie!

• Hier ist die unter Folie 2 geschilderte Implementierung gemeint.
• aus dem Originalproblem werden für jeden Primteiler q von p-1 Teilprobleme der Größe q
• diese Teilprobleme bezeichnen wir mit G^x=H mod p
• diese Teilprobleme werden mit der Pollard-folge gelöst
• es reicht, wenn Sie x mod q ausgeben
• mit PARI/gp kann man die Teillösungen über den Chinesischen Restsatz zusammensetzen

Beispiel (siehe Folie 1)

? x1=Mod(0,2)

?