Schnelle Antwort: Niemals aus praktischen Gründen. Es ist derzeit nicht von praktischem Nutzen.
Lassen Sie uns zunächst "praktische" Zusammensetzungsprüfungen von Primalitätsnachweisen trennen. Ersteres ist für fast alle Zwecke gut genug, obwohl es verschiedene Teststufen gibt, die die Menschen für angemessen halten. Für Zahlen unter 2 ^ 64 sind nicht mehr als 7 Miller-Rabin-Tests oder ein BPSW-Test für eine deterministische Antwort erforderlich. Dies ist wesentlich schneller als AKS und in jedem Fall genauso korrekt. Für Zahlen über 2 ^ 64 ist BPSW eine gute Wahl, da einige zusätzliche Miller-Rabin-Tests auf der Basis von Zufallszahlen zu sehr geringen Kosten zusätzliches Vertrauen schaffen. Fast alle Beweismethoden beginnen (oder sollten) mit einem Test wie diesem, weil er billig ist und bedeutet, dass wir nur an Zahlen arbeiten, die mit ziemlicher Sicherheit Primzahlen sind.
Weiter zu den Beweisen. In jedem Fall erfordert der resultierende Beweis keine Vermutungen, so dass diese funktional verglichen werden können. Das "gotcha" von APR-CL ist, dass es nicht ganz polynomial ist, und das "gotcha" von ECPP / fastECPP ist, dass es Zahlen geben kann, die länger als erwartet dauern.
In der Grafik sehen wir zwei Open-Source-AKS-Implementierungen - die erste stammt aus dem v6-Papier, die zweite enthält Verbesserungen von Bernstein und Voloch und eine nette R / S-Heuristik von Bornemann. Diese verwenden eine binäre Segmentierung in GMP für die Polynom-Multiplikationen, sind also ziemlich effizient, und die Speichernutzung ist für die hier betrachteten Größen kein Problem. Sie erzeugen schöne gerade Linien mit einer Steigung von ~ 6,4 im Log-Log-Graphen, was großartig ist. Die Extrapolation auf 1000 Stellen erfolgt jedoch zu geschätzten Zeiten im Bereich von Hunderttausenden bis Millionen von Jahren, verglichen mit einigen Minuten für APR-CL und ECPP. Es gibt weitere Optimierungen, die aus dem Bernstein-Papier von 2002 vorgenommen werden könnten, aber ich denke nicht, dass dies die Situation wesentlich verändern wird (obwohl dies bis zur Implementierung nicht bewiesen ist).
Schließlich schlägt AKS die Trial Division. Das BLS75-Theorem-5-Verfahren (z. B. n-1-Beweis) erfordert eine partielle Faktorisierung von n-1. Dies funktioniert gut bei kleinen Größen, und auch wenn wir Glück haben und n-1 leicht zu faktorisieren ist, werden wir irgendwann nicht mehr mit großen Semi-Primzahlen rechnen müssen. Es gibt effizientere Implementierungen, aber es skaliert wirklich nicht über 100 Stellen hinaus. Wir können sehen, dass AKS diese Methode bestehen wird. Wenn Sie die Frage also 1975 stellten (und damals den AKS-Algorithmus hatten), könnten wir die Frequenzweiche berechnen, für die AKS der praktischste Algorithmus war. In den späten 1980er Jahren war APR-CL und andere zyklotomische Methoden der richtige Vergleich, und Mitte der 1990er Jahre mussten wir ECPP einbeziehen.
Die Methoden APR-CL und ECPP sind beide Open-Source-Implementierungen. Primo (kostenloses, aber nicht Open Source-ECPP) ist schneller für größere Ziffern und ich bin sicher, dass es eine schönere Kurve gibt (ich habe noch kein neues Benchmarking durchgeführt). APR-CL ist nicht polynomial, aber der Exponent hat einen Faktor der, wie jemand witzelte, "unendlich wird, dies aber nie beobachtet wurde". Dies lässt uns glauben, dass sich die Linien theoretisch für keinen Wert von n kreuzen würden, bei dem AKS enden würde, bevor unsere Sonne ausgebrannt wäre. ECPP ist ein Las Vegas-Algorithmus. Wenn wir eine Antwort erhalten, die zu 100% korrekt ist, erwarten wir ein Ergebnis in vermutetem (ECPP) oderLogLogLognO ( log5 + ϵ( n ) )O ( log4 + ϵ( n ) )("fastECPP"), aber es kann Zahlen geben, die länger dauern. Wir gehen daher davon aus, dass Standard-AKS bei fast allen Zahlen immer langsamer als ECPP sein wird (dies hat sich bei Zahlen mit bis zu 25.000 Stellen durchaus bewährt).
AKS kann weitere Verbesserungen aufweisen, die darauf warten, entdeckt zu werden, wodurch es praktisch wird. In Bernsteins Quartic-Arbeit wird ein AKS-basierter randomisierter -Algorithmus erörtert, und in Morains fastECPP-Arbeit werden andere nicht deterministische AKS-basierte Methoden beschrieben. Dies ist eine grundlegende Änderung, zeigt aber, wie AKS einige neue Forschungsbereiche erschlossen hat. Fast 10 Jahre später habe ich jedoch noch niemanden gesehen, der diese Methode (oder sogar Implementierungen) verwendet. Er schreibt in der Einleitung: "Ist die Zeit für den neuen Algorithmus kleiner als die Zeit , um elliptisch zu finden? Kurve Zertifikate? Mein aktueller Eindruck ist, dass die Antwort nein ist, aber dass weitere [...] Ergebnisse die Antwort ändern könnten. "O ( log4 + ϵ( n ) )( lgn )4 + o ( 1 )( lgn )4 + o ( 1 )
Einige dieser Algorithmen können problemlos parallelisiert oder verteilt werden. AKS sehr einfach (jeder Test ist unabhängig). ECPP ist nicht zu schwer. Bei APR-CL bin ich mir nicht sicher.
ECPP und die BLS75-Methoden erzeugen Zertifikate, die unabhängig und schnell verifiziert werden können. Dies ist ein enormer Vorteil gegenüber AKS und APR-CL, bei denen wir nur der Implementierung und dem Computer vertrauen müssen, von denen sie erstellt wurden.
openssl pkeyparam -text
der Hex-Zeichenfolge extrahiert wird) mit PARIsisprime
(APR-CL wie angegeben) zu überprüfen : ca. 80s auf einem schnellen Notebook. Als Referenz benötigt Chromium etwas mehr als 0,25 Sekunden für jede Iteration meiner JavaScript-Demo-Implementierung des Frobenius-Tests (der viel stärker als MR ist), sodass APR-CL sicherlich paranoid, aber machbar ist.Als ich dieses kürzlich erschienene Papier über arxiv sah, das dieses Thema eingehend / detailliert analysiert, nicht sicher ist, was die Leute darüber denken, habe ich bisher keine Reaktionen gehört, es scheint eine von Studenten erstellte These zu sein, aber möglicherweise eine der detailliertesten / umfassendsten Analysen von praktische Anwendung des Algorithmus zur Verfügung.
Deterministic Primality Testing - Verständnis des AKS-Algorithmus Vijay Menon
Leistungsstarke Algorithmen, die für die Implementierung von tcs.se zu komplex sind
quelle