P-1 Faktorisierung

Aus Rechenkraft
(Weitergeleitet von P-1)
Zur Navigation springen Zur Suche springen

Die P-1 Faktorisierung (auch Pollard-p-1-Methode genannt) dient dazu aus bereits gesiebten (siehe sieben) Zahlenbereichen weitere Kandidaten vor dem Test auf Primalität zu eliminieren.

Durch verschiedene Einstellungen (die B1- und B2-Grenze) kann man die Wahrscheinlichkeit einen Faktor zu finden erhöhen (oder verringern), was zu einer Erhöhung (oder Verringerung) des zeitlichen Aufwands führt.

Warum P-1?

Man sollte abwägen, ob es nicht eher sinnvoll ist einen Kandidaten direkt auf Primalität zu überprüfen (z.B. mit LLR), da man davon ausgehen kann, dass man dadurch mindestens den getesteten Kandidaten löschen kann, im optimalen Fall sogar eine Primzahl entdeckt, wohingegen man mit der P-1 Methode nicht sicher sein kann ob man überhaupt einen Faktor findet. Dies ist der Grund warum das Faktorisierungsverfahren nur dann sinnvoll ist, wenn in der Zeit die ein Test auf Primalität in Anspruch nehmen würde mindestens ein Faktor gefunden wird. Der Vorteil eines gefundenen Faktors liegt darin, dass für den überprüften Kandidat minestens ein Primzahltest eingespart wurde, evtl. sogar zwei, wenn man den späteren möglichen zweiten Durchlauf (Doublecheck) berücksichtigt. Die zweiten Durchläufe bei Primzahltests sind nötig, da bei einem Fehler im Test evtl. ein "false negative" (getestete Primzahl wird nicht als Primzahl gemeldet) gegeben wird. Ein gefundener Faktor kann vom Server des jeweiligen Projekts in wenigen Augenblicken überprüft werden. Somit sind Doublechecks, für Zahlen für die bereits ein Faktor gefunden wurde, nicht nötig.

Wann findet man mit P-1 einen Faktor?

Wie bereits erwähnt, gibt es die sogenannten "B-Grenzen" diese geben den Bereich an in dem ein Faktor gefunden werden kann. Das Programm läuft in zwei Phasen ab, wobei der Bereich für die erste Phase durch die B1-Grenze und der Bereich für die zweite Phase durch die B2-Grenze markiert wird. Die erste Phase dauert länger hat dafür aber sehr geringe Anforderungen an den Arbeitsspeicher. Phase 2 ist relativ kurz, hat mit steigender B2-Grenze auch hohe Anforderungen an den RAM des Systems. P-1 ist dann erfolgreich wenn alle Faktoren unterhalb der B1-Grenze liegen, und maximal ein "Ausreißer" größer als B1 aber kleiner als B2 ist. Nehmen wir zum Beispiel die Zahl "67872792749091946529" (=2^5 * 11 * 17 * 19 * 43 * 149 * 8467 * 11004397) Starte man das Programm mit B1 >= 11004397 wird man direkt in der ersten Phase eine Erfolgsmeldung bekommen und die Zweite Phase wird gar nicht erst gestartet.
Startet man das Programm mit 8467 <= B1 < 1104397 und B2 >= 11004397 wird man erst in der zweiten Phase die erhoffte Meldung erhalten.
Bei 8467 <= B1 < 1104397 und B2 < 11004397 wird kein Faktor gefunden.
Sollte B1 < 8467 gewählt werden wird zwar die zweite Phase gestartet, aber unabhängig von der Größe der B2-Grenze wird kein Faktor gefunden werden.
Es ist also zu überlegen ob es sinnvoll ist überhaupt mit einer B2-Grenze zu testen, denn nur wenn es höchstesn einen Wert gibt der größer als B1 aber kleiner oder gleich B2 ist, werden auch die Faktoren für die zu testende zahl gefunden.

Projekte die P-1 Faktorisierungen durchführen

Riesel Sieve

Seventeen or Bust

XYYXF (nicht als Hauptprogramm)

Programme die benutzt werden

Prime 95 (Windows) Anleitung für Riesel-Sieve

mprime (Linux)