Strengthening the Baillie-PSW primality test
Date
2021
Authors
Baillie, Robert
Fiori, Andrew
Wagstaff, Samuel S.
Journal Title
Journal ISSN
Volume Title
Publisher
American Mathematical Society
Abstract
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)
Description
Author original manuscript (preprint)
Keywords
Primality test , Lucas sequences , Baillie-PSW , Pseudoprimes
Citation
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