Weitere Details zum Baillie-PSW-Test

Es ist klar, dass Mathematica den Baillie-PSW-Test für seine PrimeQ-Funktion verwendet (die die Primalität testet), und wie ich in der Mathematica-Dokumentation gelesen habe , beginnt er mit der Testteilung, dann mit dem Miller-Rabin-Test der Basis 2 und 3 und dann mit dem Lucas-Pseudoprime-Test. Meine Frage ist:

Können wir Basis 2 und 3 entfernen und nur eine zufällige Basis verwenden?

Kann jemand außer Wikipedia eine gute Referenz zu diesem Primalitätstest vorschlagen ?

Der Vorteil bei der Verwendung von Basis 2 besteht darin, dass wir die gesamte Basis 2 des PSP bis zu . Es wurde verifiziert, dass keiner dieser psp (2) einen Lucas-Test besteht, wenn die Parameter in Übereinstimmung mit einer der Methoden im Baillie / Wagstaff-Papier ausgewählt werden.$2^{64}$$P, Q$

Wenn Sie eine zufällige Basis wählen, gibt es möglicherweise ein zusammengesetztes , das sowohl den Fermat- als auch den Lucas-Test besteht. Zum Beispiel ist eine starke psp-Basis 76 und auch ein Lucas-Pseudoprime.$n$$n = 5777$

Übrigens, wenn Sie einen Lucas-Test implementieren, würde ich auch empfehlen, die folgende Prüfung hinzuzufügen, die praktisch kostenlos ist, sobald Sie das Ende der Lucas-Berechnung erreicht haben. Wenn eine ungerade Primzahl ist und wobei , (und wie üblich (ein Jacobi-Symbol) ), dann . Wenn und nach Methode (siehe Baillie / Wagstaff), dann ist 913 die einzige ungerade zusammengesetzte Zahl bis zu 25 Milliarden für was diese Kongruenz gilt. (Das S / W-Papier gibt eine Grenze von$n$$(n, QD) = 1$$D = P^2 - 4Q$$\left(\frac{D}{n}\right) = -1$$V_{n+1} \equiv 2Q \pmod n$$D, P$$Q$$A^*$$10^8$, aber ich habe die Berechnung vor kurzem weiter getragen). Zusätzlich zu den Sprp (2) - und Slprp (P, Q) -Tests verleiht diese Kongruenz dem Primalitätstest zusätzliche Stärke.

Referenzen für den Test:

• Pomerance, Selfridge, Wagstaff, " The Pseudoprimes to 25 x 10 ^ 9 ", Juli 1980. Seite 1024-1025, Überprüfen Sie, ob n eine starke wahrscheinliche Primzahl ist. 2. Überprüfen Sie, ob n eine Lucas-wahrscheinliche Primzahl ist, indem Sie Methode A (Selfridge) verwenden. oder B. Die Autoren bieten dem ersten Finder eines Gegenbeispiels oder eines Nachweises der Nichtexistenz 30 USD an. Bei der Erörterung des Tests wird auf das nächste Papier verwiesen.

• Baillie und Wagstaff, " Lucas Pseudoprimes ", Oktober 1980. Seite 1401. Der Prozess teilt sich bis zu einer geeigneten Grenze. Überprüfen Sie mit Methode A (Selfridge) oder B, ob n eine starke wahrscheinliche Primzahl ist. 2. Überprüfen Sie, ob n eine starke wahrscheinliche Lucas-Primzahl ist.

• Pomerance, " Gibt es Gegenbeispiele zum Baillie-PSW-Primalitätstest? ", 1984. Literatur PSW80: Überprüfen Sie mit den Selfridge-Parametern (Methode A), ob n eine starke wahrscheinliche Primzahl ist. 2. Überprüfen Sie, ob n eine Lucas-wahrscheinliche Primzahl ist. . Er erwähnt, dass selbst wenn Bedingung 1 geschwächt ist, jedes Komposit auf n <= 25 * 10 ^ 9 immer noch fehlschlägt. Das kurze Papier nennt diese Kombination aus einem starken Base-2-Prp und Lucas-Selfridge-Prp wiederholt den "Baillie-PSW" -Test.

Alle diese beschreiben die Verwendung eines starken Basis-2-Wahrscheinlichkeitstests. Das etwas frühere PSW-Papier weist auf einen Lucas-Test hin, während das BW-Papier einen starken Lucas-Test empfiehlt. Die Arbeiten von 1980 weisen darauf hin, dass eine von zwei spezifischen Methoden zur Parameterauswahl verwendet werden sollte, während die Arbeit von Pomerance aus dem Jahr 1984 die Nicht-Selfridge-Methode fallen lässt.

Meiner Meinung nach ist das Papier von Baillie und Wagstaff die Hauptreferenz, sollte jedoch in Kombination mit Pomerance, Selfridge und Wagstaff gelesen werden. Im Laufe der Zeit besteht Konsens darüber, dass die Selfridge-Parameterauswahl (Methode A) verwendet werden sollte. Andere üblicherweise verwendete Variationen umfassen den extra starken Test, den "fast" extra starken Test und den Frobenius-Test. Weitere Informationen und Links finden Sie auf der Seite " Pseudoprime-Statistiken, Daten und Tabellen ".

So beantworten Sie Ihre Mathematica-Fragen:

1. Basierend auf Pinch (1993) führte Mathematica einen starken Pseudoprime-Test der Basis 2 durch, wie es sollte, verwendete jedoch einen borked "Lucas" -Test, der nicht der Test von Baillie et al. angegeben. Pinch fand Pseudoprimes zu ihrem Test. Er weist auch darauf hin, dass Wolfram seinen Lucas-Test in irgendeiner Weise modifiziert hat, jedoch nicht den Lucas-Test, der für BPSW verwendet werden sollte. Ohne Informationen von Wolfram wissen wir nicht, was sie in den letzten 24 Jahren seitdem getan haben. Vielleicht haben sie ihren "Lucas" -Test verbessert und den Base-3-MR-Test hinzugefügt, um Probleme zu vertuschen. Vielleicht verwenden sie jetzt einen richtigen Lucas-Test. Wir wissen es nicht.

2. Wenn der richtige Lucas-Test verwendet würde, könnte der Basis-3-Test entfernt werden, und wir hätten einen ähnlichen BPSW-Test wie die meisten anderen Pakete. Wir würden wissen, dass es absolut keine Gegenbeispiele unter 2 ^ 64 und keine größeren Gegenbeispiele gab. Das Hinzufügen eines weiteren Tests, egal ob Basis 3 oder zufällige Basis, würde die Sicherheit für> 64-Bit-Eingaben erhöhen. Ich denke nicht, dass das eine schlechte Idee ist.

3. Das Ersetzen des Base-2-Tests durch einen Random-Base-Test ist meiner Meinung nach eine schlechte Idee. Wir haben bekannte Ergebnisse für die Verwendung von Basis 2, einschließlich der sehr schönen No-64-Bit-Gegenbeispiele. Es macht den Test deterministisch. Die Verwendung einer zufälligen Basis behält zwar die Antikorrelationseigenschaft in Bezug auf den Lucas-Test bei, weist jedoch unterschiedliche Kompromisse auf. Persönlich denke ich, dass es eine bessere Idee ist, einen richtigen BPSW-Test (Basis 2 SPRP + stark / AES / ES Lucas) plus einen oder mehrere Tests auf zufälliger Basis zu verwenden, wenn Sie Gegner besiegen möchten, die BPSW-Pseudoprimes heimlich kennen. Oder fügen Sie die zusätzliche Arbeit für einen Frobenius-Test zusätzlich zum Lucas-Test hinzu.

Sie stellen zwei Fragen. Ich werde nur die erste beantworten.

Es ist sehr wahrscheinlich, dass Mathematica den Basis 2- und 3-Test als Optimierung verwendet . Diese Basen sind wahrscheinlich schneller zu testen (aufgrund ihrer Größe) und funktionieren für beide Zahlen. Sie können diesen Test überspringen, wenn Sie möchten, aber die resultierende Funktion wäre im Durchschnitt langsamer.