Primfaktorzerlegung

Bei Eingabe einer natürlichen Zahl > 1 und Wahl eines Verfahrens wird versucht, einen Faktor dieser Zahl zu berechnen.
Damit das Applet funktioniert, muß Java installiert und aktiviert sein.

Für einen Test kann der folgende Primzahlgenerator verwendet werden.
Der berechnet das Produkt aus zwei Primzahlen einstellbarer Bitlänge.

Verwendung des Applets

Die zu zerlegende Zahl (die beliebig groß sein darf) in das Eingabefeld kopieren und ein Verfahren auswählen. Je nachdem müssen noch zusätzliche Parameter eingegeben werden (die Voreinstellungen sind eigentlich immer brauchbar). Um sicherzustellen, daß keine Primzahl vorliegt, kann ein zusätzlicher Primzahltest (nach Miller-Rabin) gemacht werden. Nach Klick auf Start wird das entsprechende Verfahren gestartet. Der Rechenaufwand hängt stark vom gewählten Algorithmus ab und sollte nicht unterschätzt werden. Man sollte sich nicht der Illusion hingeben, beliebige 100stellige Zahlen faktorisieren zu können!

Um die verschiedenen Verfahren zu testen, kann der Primzahlgenerator verwendet werden. Dieser erzeugt das Produkt p·q zufällig generierter Primzahlen p und q, wobei die Größe über die Schieberegler festgelegt werden kann. Nach Klick auf Erzeugen erscheint das Produkt im oberen Textfeld, von wo aus es kopiert werden kann.

Algorithmen zur Faktorisierung

Im folgenden eine kurze Vorstellung der Algorithmen. Interessant ist, daß bei den meisten Zufall im Spiel ist, d. h. man kann nicht genau vorhersagen, ob und wann ein Teiler gefunden wird.

Probedivision
Der naive Algorithmus: Man probiert einfach alle möglichen Kandidaten durch, bis man den gesuchten Teiler findet. Mit diesem Ansatz können kleine Teiler sehr schnell gefunden werden. Eine Verbesserung ergibt sich durch die Überlegung, daß alle Vielfachen eines Nichtteilers k auch Nichtteiler sind. Im Applet wird die Eingabezahl nacheinander durch 2, 3, 5 und (aufsteigend) alle Zahlen dividiert, die prim sind modulo 30.

Fermat-Verfahren
Die Idee dieses Verfahrens geht auf einen Brief Fermat's aus dem Jahre 1632 zurück: Die Eingabezahl N wird als Differenz zweier Quadrate dargestellt. Wenn man zwei solche Quadrate findet, dann liefert

N = x² - y² = (x - y)(x + y)

eine Faktorzerlegung! Ausgehend von √N wird für alle x die Differenz N - x² daraufhin getestet, ob sie ein Quadrat ist oder nicht. Der Nachteil dieser Methode ist, daß nur solche Faktoren schnell gefunden werden können, die sehr dicht beieinander liegen.

(p-1)-Verfahren
Dieses Verfahren benutzt den Satz von Fermat, der besagt, daß jede Primzahl p ein Teiler von ap-1 - 1 ist (sofern a nicht durch p teilbar ist). Ausgehend von einem Element a kann man durch sukzessives Potenzieren mit Primzahlen q darauf hoffen, daß irgendwann einmal ak - 1 durch p teilbar ist - dann liefert uns nämlich ggT(ak - 1, N) i. a. den gesuchten Primfaktor p.
Ob und wann dieser Fall eintritt, ist ein reines Glücksspiel, denn es stellt sich heraus, daß wir nur dann Erfolg haben, falls der zweitgrößte Primteiler von p-1 kleiner als eine Schranke B1 und der größte kleiner als eine Schranke B2 ist. Je größer diese Schranken zu wählen sind, umso länger dauert die Berechnung (im Applet können B1 und B2 frei eingestellt werden).

Pollard-Rho
Dieses sehr elegante Verfahren wurde 1975 von John M. Pollard erfunden. Statt direkt nach einem Teiler p zu suchen, konstruiert man stattdessen zwei Zahlen xi und xj, deren Differenz xi - xj durch p teilbar ist (dann erhält man p durch Berechnung von ggT(xi - xj, N)). Diese Zahlen erzeugt man durch die rekursive Vorschrift xi+1 = xi² + a. Die so erzeugte Folge wird modulo p periodisch, d. h. für zwei Folgenglieder xi und xj ist p | (xi - xj). Aufgrund probabilistischer Überlegungen ist die Periodenlänge viel kleiner als p, so daß man die entsprechenden xi, xj recht schnell findet. Wie lange es wirklich dauert, hängt aber stark vom Zufall ab. Auch der Parameter a spielt eine Rolle - je nach Wahl von a wird man früh oder erst sehr spät fündig - das weiß man aber leider nicht vorher.

Methode der elliptischen Kurven (ECM)
Ein vielleicht nicht ganz so naheliegender Ansatz ist folgender: Um einen Primteiler p zu finden betrachtet man Punkte (x, y) der Form

y² = x³ + ax + b

wobei x, y aus dem Restklassenring modulo p und a, b ganze Zahlen sind. Man kann zeigen, daß diese "elliptische Kurve" eine abelsche Gruppe ist, d. h. es ist möglich, beliebige Punkte auf der Kurve zu addieren bzw. zu invertieren. Um p zu finden, wird nun versucht, das neutrale Element Op durch Punktadditionen zu konstruieren. Ob das gelingt, hängt entscheidend von der Gruppenordnung ab. Sind alle ihre Primteiler kleiner als eine Schranke B2, so hat man (ähnlich dem (p-1)-Verfahren) eine Chance - ansonsten eben Pech. Über die Kurvenparameter kann man auf die Ordnung Einfluß nehmen, der genaue Effekt ist allerdings nicht vorhersagbar. Zumindest kann man sich Hoffnung machen auch jene etwas größeren Teiler zu finden, für die das (p-1)-Verfahren versagt bzw. die für die anderen Verfahren außer Reichweite liegen.
Die optimalen Werte für die Schranken B1, B2 hängen von der Größe des zu findenden Primteilers p ab - der dummerweise nicht bekannt ist. Nach etlichen Testreihen habe ich folgende Werte (die vermutlich dicht am Optimum liegen) gefunden:

BitlängeB1B2Kurven
407003500019
50280013500033
60950051000063

(Das optimale Verhältnis B2/B1 scheint bei etwa 50 zu liegen.) Man kann beispielsweise 19 Kurven mit der Einstellung 700/35000 berechnen lassen und bei Mißerfolg mit 33 Kurven bei 2800/135000 fortsetzen. Bei der Anzahl der zu berechnenden Kurven handelt es sich wirklich nur um einen Mittelwert. Wie man leicht mit dem Applet ausprobieren kann, variiert die genaue Zahl spürbar.


Autor: Kay Schönberger
zuletzt geändert am: 08.01.2007
Verbesserungsvorschläge an: schoenbe (at) informatik.hu-berlin.de
Statistik:
perfumes