  The Baillie-PSW primality test combines Fermat and Lucas probable prime
tests. It reports that a number is either composite or probably prime. No odd
composite integer has 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 what we call
Lucas-V pseudoprimes, of which there are only five less than $10^{15}$.
