Lektion Pollard und Chinese Remainder Theorem

Anleitung zum Selbstudium

das Problem des Shanks-Algorithmus (siehe letzte Lektion) ist der hohe Speicherplatzverbrauch
für eine 50-stellige Primzahl p wird hier ausgerechnet, dass man sehr viele Petabytes bräuchte, um die Lookup-Tabelle zu speichern, der Zugriff muss schnell sein, daher wäre RAM nötig, heutige RAM-Größen enden bei etwa 1 TB (wer es genauer recherchiert hat, bitte melden, interessiert mich)
(in einem gewissen Bereich) praktikable weitere Verfahren vermeiden diese Speicherplatzanforderung, diese gehen auf Pollard zurück

bevor wir uns den Pollard Ideen zuwenden, lernen wir etwas über die Reduzierung des Problems, die dann funktioniert, wenn alle Teiler von p-1 unterhalb einer gewissen Schranke liegen (etwa 25 Dezimalstellen oder 80 Bits)
oben sieht man die Primfaktorzerlegung von p-1, es gebe r Primfaktoren, die Originalgleichung wird für jeden Primfaktor q mit dem Exponent (p-1)/q potenziert
dadurch gewinnt man folgendes: gibt es im Originalproblem noch die Möglichkeiten {1,2,3,...,p-1} für x, so gibt es in jeder der r neuen Gleichungen nur noch die Möglichkeiten {1,2,3,...,q-1}, wobei q für eines der q's aus der Primfaktorzerlegung steht

das Ganze sehen wir am Beispiel 2^x = 6 mod 11
es gibt zwei q's
für jedes q machen wir die Potenzierung
für q=2 gibt es zwei Lösungsmöglichkeiten, also kann man einfach durch Einsetzen ausprobieren, welche passt, hier passt x=1, genauer gesagt ist sogar x = 1 mod 2 richtig
für q=5 gibt es fünf Lösungsmöglichkeiten, wieder kann man einfach durch Einsetzen ausprobieren, welche passt, hier passt x=4, genauer gesagt ist sogar x = 4 mod 5 richtig
wir werden das Einsetzen später mit den Pollard-Ideen beschleunigen, aber im Prinzip könnte man so schon eine relativ effiziente Methode implementieren

ein (kleines) Problem ist, man hat statt x direkt zu sehen, mehrere Teilergebnisse der Form x = a mod q
hierfür gibt es eine mathematisch exakte und effiziente Lösung: die Methode des Chinesischen Restsatzes, wird hier behandelt, aber eine Möglichkeit ihn unabhängig nachzulesen ist unter Univ Stanford

der Einschub erläutert, wie es geht
man braucht von den zwei Ausgangszeilen modulo m1 und m2 die jeweiligen Inversen, d.h. 1/m1 mod m2 und 1/m2 mod m1, diese werden m1' und m2' genannt
setzt man m1' und m2' in die gezeigte Formel für x ein, ist man fertig, man hat eine Lösung x
die Lösung ist nicht unbedingt die kleinste, daher berechnet man x mod (m1*m2)

enthält dann ein durchgerechnetes Beispiel
zum Lernen empfiehlt es sich, dieses Beispiel auf einem leeren Blatt selbst zu rechnen
da dies öfters in der Kryptographie vorkommt, empfiehlt es sich, diese Technik an selbstgewählten Beispielen zu üben, man kann das sehr gut selber überprüfen
nehmen Sie z.B. die Aufgabe "ich habe eine Menge Schokobonbons, verteile ich sie gleichmäßig auf drei Kinder, bleiben zwei übrig, würde ich sie jedoch an 7 Kinder verteilen, blieben drei übrig, wieviele Schokobonbons hatte ich vor dem Verteilen?"
in Formeln sieht das so aus: x = 2 mod 3 und x = 3 mod 7, lösen Sie das mit der gezeigten Methode
es sollte x = 17 herauskommen (mod 21)

zeigt die Pollard-Rho-Zahlenfolge, der griechische Buchstabe Rho kommt von der Skizzierung des Verfahrens, die Folge läuft eine Weile vorwärts, bis sie einen Punkt erreicht, an dem sie schon war und ab diesem Zeitpunkt im Kreis siehe etwa Rho

zeigt ein Beispiel, das zunächst durch die Exponentiation reduziert wird und dann gibt es bei 2^x = 6 mod 23 nur noch 11 Möglichkeiten, weil diese Gleichung im Fall q=11 erreicht wird

die Definition der Zahlenfolge sieht man im roten Kasten
dazu gibt es ein Beispiel, man kann mit jedem Startwert für k und l beginnen, wir beginnen mit k=l=1
je nach Fallunterscheidung (siehe roter Kasten) wird entweder
- mit g multipliziert (der Exponent von g, also k wird dadurch erhöht)
- mit h multipliziert (der Exponent von h, also l wird dadurch erhöht)
- quadriert (beide Exponenten k und l werden verdoppelt)
die Lösung x wird dann mod q ausgerechnet und zwar nach der untenstehenden Formel

setzen Sie diese Rechnung fort (diesmal ohne Pollard) für den Fall q=2, dadurch gibt es nur zwei Möglichkeiten für x
aus Folie 9 wissen wir x=9 mod 11, Sie erhalten entweder x = 0 oder x = 1 mod 2 aus der Betrachtung für q=2
daraus können Sie mit dem chinesischen Restsatz zusammensetzen, was x mod 22 ist
Übung: Programmieren Sie! Diese Zahlenfolge zu programmieren, braucht nur wenige Zeilen Code. Es lohnt sich diese zu programmieren. Genießen Sie für eine Weile endlose Zahlenfolgen.
Sie können das Beispiel von Folie 9 als Testparameter wählen.
Jetzt erweitern Sie das Programm: das Programm soll abbrechen, wenn sich die Ausgabe wiederholt.
das bringt uns auf ein Programmierproblem: woher weiß man, dass die Folge an einem Punkt angelangt ist, an dem sie sich wiederholt? Versuchen Sie einen Abbruch der Schleife zu programmieren...
beim nächsten Mal sehen wir, wie's geht