Strengthening the Baillie-PSW primality test

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)