Strengthening the Baillie-PSW primality test
Wagstaff, Samuel S.
American Mathematical Society
In 1980, the first and third authors proposed a probabilistic primality test that has become known as the Baillie-PSW primality test. Its power to distinguish between primes and composites comes from combining a Fermat probable prime test with a Lucas probable prime test. No odd composite integers have been reported to pass this combination of primality tests if the parameters are chosen in an appropriate way. Here, we describe a significant strengthening of this test that comes at almost no additional computational cost. This is achieved by including in the test Lucas-V pseudoprimes, of which there are only five less than 10 (15)
Author original manuscript (preprint)
Primality test , Lucas sequences , Baillie-PSW , Pseudoprimes
Baillie, R., Fiori, A., & Wagstaff, S. S. (2021). Strengthening the Baillie-PSW primality test. Mathematics of Computation, 90(330), 1931-1955. https://doi.org/10.1090/mcom/3616