Baillie-PSW-Primzahltest

Der Baillie-PSW-Primzahltest (benannt nach Robert Baillie, PSW steht für die Co-Autoren Carl Pomerance, John Selfridge und Samuel Wagstaff) ist ein effizienter, heuristischer Test, um zu bestimmen, ob eine natürliche Zahl prim ist. Es handelt sich um keine eigene Kategorie von Test, sondern stattdessen um eine Kombination des Miller-Rabin-Tests zur Basis 2 mit einem starken Primzahltest auf Basis einer Lucas-Folge, deren Parameter nach einem Algorithmus von John Selfridge bestimmt werden (für die zu testende Zahl $n$):

1. Bestimme das erste $D$ in der Folge 5, -7, 9, -11, …, so dass $\left({\frac {D}{n}}\right)=-1$ (Jacobi-Symbol).
2. Setze $P=1$ und $Q={\frac {1-D}{4}}$ (Parameter für die Lucas-Folge, siehe dort).

Bei der Implementierung sollte beachtet werden, dass kein solches $D$ existiert, falls $n$ eine Quadratzahl ist. Schlägt die Suche also wiederholt fehl, muss zunächst durch Ziehen der Quadratwurzel von $n$ geprüft werden, ob dies der Fall ist. Außerdem sind gewisse Optimierungen möglich, z. B. muss $D=9$ nicht geprüft werden, da 9 selbst eine Quadratzahl ist, und das Jacobi-Symbol deswegen nur 0 oder 1 sein kann.

Beide Einzeltests haben viele bekannte Pseudoprimzahlen, jedoch wurde bisher keine zusammengesetzte Zahl veröffentlicht, die beide Einzeltests gleichzeitig besteht. Speziell wurde auch anhand einer kompletten, computergenerierten Liste der Fermatsche Pseudoprimzahlen zur Basis 2 (eine Obermenge der Miller-Rabin-Pseudoprimzahlen zur gleichen Basis) bis $2^{64}$ verifiziert, dass der Baillie-PSW-Test bis mindestens zu dieser Grenze frei von Pseudoprimzahlen ist.

Auf das Auffinden einer Pseudoprimzahl, die bestimmte zusätzliche Bedingungen erfüllt, ist eine Belohnung mehrerer Autoren von insgesamt 620 Dollar ausgesetzt, ebenso wie für den Beweis, dass keine Pseudoprimzahlen existieren. Jedoch gibt es ein heuristisches Argument von Pomerance selbst, nach dem der Test unendlich viele Pseudoprimzahlen habe.

Der Baillie-PSW-Test ist heuristisch, da nicht bewiesen ist, dass es für ihn keine Pseudoprimzahlen gibt. Er sollte nicht mit einem probabilistischen Test verwechselt werden, da die Parameterauswahl fest vorgegeben und nicht zufällig ist, und eine Wiederholung mit anderen Parametern zur Erhöhung der Konfidenz ebenfalls nicht vorgesehen ist – auch wenn eine solche Wiederholung relativ leicht umzusetzen ist.