Strengthening the Baillie-PSW primality test

Principal Investigator: Samuel Wagstaff

In 1980, Baillie and Wagstaff proposed a probabilistic primality test that has become known aa the Baillie-PSW primality test.  It is widely used in internet security.  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 integer has ever been found to pass this combination of primality tests. We describe a significant strengthening of this test that comes at almost no additional cost. This is achieved by including in the test Lucas-V pseudoprimes, of which there are only five below 10^15.

Personnel

Other PIs: Robert Baillie Andrew Fiori

Keywords: Lucas sequence, Primality test