Diskussion:Dixons Faktorisierungsmethode
Optimierungsmöglichkeit speziell für Dixons Faktorisierungsmethode
[Quelltext bearbeiten]Eine nicht unerhebliche Optimierungsmöglichkeit speziell für die Dixon Faktorisierungsmethode wurde bisher nicht erwähnt. Da man aber damit die durchschnittliche Laufzeit manchmal fast bis auf die Hälfte reduzieren kann, sollte sie meines Erachtens auf der deutschen Web-Site auch Erwähnung finden.
Man generiert am Anfang der Dixon-Faktorisierungsmethode direkt nach der Bestimmung der Faktorbasis auch das Produkt P aus allen positiven Faktoren dieser Faktorbasis. Dann testet man für jeden generierten Y-Wert mit Hilfer wiederholter Anwendung des gcd, ob dieser Y-Wert vollständig glatt bezüglich der Faktorbasis ist.
Sei Q = gcd(Y, P). Wenn (Q = 1) ist, enthält der aktuelle Y-Wert keinen einzigen Faktor aus der Faktorbasis (mehr). Somit kann dieser Y-Wert getrost ignoriert werden. Solange aber (Q > 1) ist, enthält der aktuelle Y-Wert mindestens noch einen (oder mehrere Faktoren) der Faktorbasis und ist somit zumindest teilweise glatt. Nun teilt man den aktuellen Y-Wert durch seinen (bisher ermittelten) glatten Anteil Q also Y = (Y / Q) und bestimmt erneut Q = gcd(Y, Q), solange bis (Q = 1), was meist recht schnell passiert, da nur selten höhere Potenzen der Faktoren aus der Faktorbasis vorkommen. Bleibt zum Schluss (also bei (Q = 1)) ein (abs(Y) > 1) übrig, ist der aktuelle Y-Wert nicht vollständig glatt und kann daher ebenfalls ignoriert werden. Ist aber am Ende (abs(Y) = 1), so ist der aktuelle Y-Wert vollständig glatt bezüglich der Faktorbasis. Nur wenn genau das der Fall ist, beginnt man den vollständig glatten Y-Wert durch alle positiven Faktoren der Faktorbasis zu teilen, um dessen Faktorisierung zu erhalten. Auf diesem Wege werden alle zeitaufwendigen Probedivisionen von nicht vollständig glatten Y-Werten komplett eingespart und durch jeweils eine oder wenige gcd-Bestimmungen ersetzt, was ganz offensichtlich deutliche Laufzeitverbesserungen mit sich bringt.
Man sollte noch anmerken, dass die hiermit erzielbaren Laufzeitverbesserungen um so größer werden, je mehr Probedivisionen damit eingespart werden können. Das wiederum ist meistens dann der Fall, wenn die zu faktorisierenden Zahlen größer werden und damit zwangsweise mehr Faktoren in der Faktorbasis sind, bzw. bei gleich großer Faktorbasis die vollständig glatten Zahlen schwer zu finden sind und deshalb sehr viele (und damit auch größere) Y-Werte generiert werden müssen. Nur wenn fast jeder generierte Y-Wert vollständig glatt bezüglich der Faktorbasis ist (was ich aber bisher außer bei viel zu großen Faktorbasen noch nicht gesehen habe), erzeugt man damit einen entsprechenden Mehraufwand.
--Aragorn321 (Diskussion) 14:31, 3. Jul. 2013 (CEST)
Optimierungsmöglichkeit für alle Dixon-artigen Faktorisierungsmethoden
[Quelltext bearbeiten]Unter dem Begriff "Dixon-artige Faktorisierungsmethode" seien hier all jene Faktorisierungsmethoden zusammengefasst, welche zu erst in einer sogenannten Datensammelphase (DSP) eine ausreichende Menge von glatten Kongruenzen in einer Binärmatrix M sammeln, um diese dann in einer sich anschließenden Datenverarbeitungsphase (DVP) z.B. mit Hilfe des Gaußschen Eliminierungsverfahren zu verarbeiten. Hierunter fallen zumindest die Kettenbruchmethode, die Dixon-Faktorisierungsmethode und das Quadratische Sieb.
Das Problem, welchses man bei diesem Vorgehen generell hat, ist das folgende: Zum Zeitpunkt der DSP weiß man leider nicht genau, wieviele glatte Kongruenzen man in der DVP tatsächlich benötigt. Die Aussage, das man K+1 solcher Kongruenzen mindestens benötigt, wenn K die Anzahl aller Faktoren in der Faktorbasis ist, stimmt so allgemein nicht. Zum einen ist sie zu viel zu ungenau und zum anderen werden oft erheblich weniger als K glatte Kongruenzen benötigt, um einen nichttrivialen Teiler der zu faktorisierenden Zahl N zu finden. Es gibt aber auch Fälle, wo K+1 glatte Kongruenzen noch lange nicht ausreichen, um einen nichttrivialen Teiler der zu faktorisierenden Zahl N zu finden. Also ist man quasi gezwungen, in der DSP "auf jeden Fall ausreichend viele" also (K+T) glatte Kongruenzen zu sammeln, damit zum Schluß in der DVP die Bestimmung eines nichtrivialen Faktors von N immer noch möglich ist.
Nun ist aber bekannt, dass man die ersten glatten Kongruenzen meist recht schnell findet, da zu Anfang die generierten und auf Glattheit zu testenden Y-Werte betragsmäßig gesehen noch relativ klein sind und es daher verhältnismäßig viele glatte Werte gibt. Aber genau nach den letzten glatten Kongruenzen sucht man "ewig", weil die generierten Y-Werte betragsmäßig gesehen nun nicht mehr so klein sind und es daher verhältnismäßig viel viel weniger glatte Werte gibt. Es wäre also daher äußerst sinnvoll, wenn man am Anfang nur genau soviele glatte Kongruenzen einsammelt, wie man dann zum Schluß auch tatsächlich benötigt.
Dazu ist es aber erforderlich, die beiden nacheinander ausgeführten Phasen DSP und DVP der Dixon-artigen Faktorisierungsmethode aufzulösen, um die Verarbeitung einer jeden gefundenen glatten Kongruenz auch sofort zu beginnen. Erhält man als Ergebnis der Verarbeitung einer neu gefundenen glatten Kongruenz einen nichttrivialen Faktor der zu faktorisierenden Zahl N, so kann man die Faktorisierung der Zahl N an dieser Stelle beenden. Hat man aber einen solchen nichttrivialen Faktor (noch) nicht gefunden, sucht man die nächste glatte Kongruenz, und verarbeitet diese, usw. bis man (endlich) einen solchen nichttrivialen Faktor gefunden hat. Mit diesem Vorgehen sollte es möglich sein, stets nur genau soviel glatte Kongruenzen zu generieren, wie tatsächlich auch benötigt werden. Wenn man auf diesem Wege 10%, 20% oder gar 25% an zu generierenden glatten Kongruenzen einsparen kann, spart man oft erheblich mehr Laufzeit ein als 10%, 20 oder gar 25%, da dies ja die letzten und somit am schwersten zu findenden glatten Kongruenzen sind.
Um die Verarbeitung einer gefundenen glatten Kongruenz auch sofort beginnen zu können, startet man mit einer leeren binären quadratischen Matrix M der Dimension K. Hat man eine neue glatte Kongruenz Yi gefunden, bestimmt man sofort auch deren binären Exponentenvektor Ei = (ei,0, ei,1, ... ei,k-1), wo ja alle ei,j binäre Werte {0,1} sind. Solange Ei nicht komplett Null ist, kann man auch dessen Grad G bestimmen, welches nichts anderes ist, als der Index des höchsten gesetzten Bits, also max(j) mit (ei,j = 1). Nun untersucht man, ob die Zeile G in der Matrix M noch leer also komplett Null ist. Wenn ja, trägt man den aktuellen Ej dort unverändert ein, um die nächste glatte Kongruenz zu suchen. Enthält die Matrix M aber schon eine Zeile EG, so hat diese ebenfalls den Grad G und man kann EG auf das aktuelle Ei (mit xor) drauf addieren, welches als Resultat der XOR-Operation nun entweder komplett Null ist, oder andernfalls einen neuen Grad hat, welcher definitiv kleiner als G ist.
Auf diesem Wege wird Schritt für Schritt ein linear unabhängiges Gleichungssystem aufgebaut. Konkret sieht dass so aus, dass M eine binäre Dreiecksmatrix wird, deren obere rechte Hälfte komplett Null ist. Die Hauptdiagonale wird solange mit neuen Einsen bevölkert, wie man eine neue linear unabhägige Kongruenz (also mit Ei nicht komplett Null) gefunden hat. Ist dagegen Ei (nach irgendeiner XOR-Operation) komplett Null, hat man schon eine linear abhängige Kombination von Binärvektoren gefunden (auch dann, wenn M noch viele Leerzeilen hat) und man sollte auch sofort den gcd-Test machen, ob man tatsächlich schon einen nichttrivialen Teiler der zu faktorisierenden Zahl N gefunden hat.
Als wunderbarer Nebeneffekt der Tatsache, dass man nun nicht mehr gezwungen ist, jedesmal vorbeugend ausreichend viele (also K+T) glatte Kongruenzen zu sammeln, sondern nur noch genau so viele glatte Kongruenzen suchen muss, wie man tatsächlich auch benötigt, kann man S, die "smoothness bound" (dafür fällt mir im Moment auch als Muttersprachler kein guter deutscher Begriff ein) im gewissen Rahmen gefahrlos vergrößern, was zwar zu mehr Faktoren K in der Faktorbasis führt, aber dafür die Wahrscheinlichkeit an glatten Y-Werten drastisch erhöht und somit die Laufzeit weiter reduziert. So kann man z.B mit K = 2 * 500 = 1000 statt K = 1 * 500 arbeiten, benötigt aber vielleicht trotzdem nur ca. 800 verschiedene glatte Kongruenzen bis man einen nichttrivialen Faktor von N gefunden hat, d.h. die Matrix M hat auch maximal ca. 800 nicht leere Zeilen, wahrscheinlich sogar weniger, denn es liefert ja nicht jede linear abhängige glatte Kongruenz einen nichttrivialen Teiler von N.