Baillie PSW prime number test

The Baillie PSW prime number test (named after Robert Baillie , PSW stands for co-authors Carl Pomerance , John Selfridge, and Samuel Wagstaff ) is an efficient, heuristic test for determining whether a natural number is prime . It is not a separate category of test, but instead a combination of the Miller-Rabin test for base 2 with a strong prime number test based on a Lucas sequence , the parameters of which are determined according to an algorithm by John Selfridge (for the test to be tested Number ): ${\displaystyle n}$

1. Find the first in the sequence 5, -7, 9, -11,… so that ( Jacobi symbol ). ${\displaystyle D}$ ${\displaystyle \left({\frac {D}{n}}\right)=-1}$
2. Set and (parameters for the Lucas sequence, see there ). ${\displaystyle P=1}$ ${\displaystyle Q={\frac {1-D}{4}}}$

During the implementation it should be noted that if is a square number , there is none . If the search fails repeatedly, you must first check whether this is the case by pulling the square root of . In addition, certain optimizations are possible, e.g. B. does not have to be checked, since 9 is itself a square number and the Jacobi symbol can therefore only be 0 or 1. ${\displaystyle D}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle D=9}$

Both individual tests have many known pseudoprimes , but no composite number has yet been published that passes both individual tests at the same time. In particular, a complete, computer-generated list of Fermat's pseudo-prime numbers on base 2 (a superset of Miller-Rabin pseudo-prime numbers on the same base) was used to verify that the Baillie-PSW test is free of pseudo-prime numbers up to at least this limit. ${\displaystyle 2^{64}}$

A multi-author reward totaling $ 620 is available for finding a pseudoprime that meets certain additional conditions, as well as proving that no pseudoprimes exist. However, there is a heuristic argument from Pomerance himself that the test has an infinite number of pseudoprimes.

The Baillie PSW test is heuristic because it has not been proven that there are no pseudo-prime numbers for it. It should not be confused with a probabilistic test, as the parameter selection is fixed and not random, and repetition with other parameters to increase confidence is also not intended - even if such a repetition is relatively easy to implement.

Individual evidence

1. ^ Robert Baillie, Samuel S. Wagstaff, Jr .: Lucas Pseudoprimes . In: Mathematics of Computation . 35, No. 152, October 1980, pp. 1391-1417. doi : 10.1090 / S0025-5718-1980-0583518-6 .
2. ↑ Are There Counterexamples to the Baillie-PSW Primality Test? , Carl Pomerance, 1984