Baillie-PSW Test

Essentially the Baillie-Pomerance-Selfridge-Wagstaff (BPSW) test combines a strong base $2$ Fermat probable prime test with a Lucas probable prime test whose parameters are chosen by one of two methods due to Selfridge and Wagstaff respectively.

Selfridge's choice is: Let $\Delta$ $=$ $P^2$ $-$ $4Q$ be the first from $[5,$ $-7,$ $9,$ $-11,$ $13,$ $\ldots]$ for which the Jacobi symbol of $\Delta$ over $n$ is $-1$, where $P$ $=$ $1$ and $Q$ $=$ $\frac{1-\Delta}{4}$

Wagstaff's choice is: Let $\Delta$ $=$ $P^2$ $-$ $4Q$ be the first from $[5,$ $9,$ $13,$ $17,$ $21,$ $\ldots]$ for which the Jacobi symbol of $\Delta$ over $n$ is $-1$, where $P$ is the least odd number exceeding $\sqrt\Delta$ and $Q$ $=$ $\frac{P^2-4}{\Delta}$.

There is a cut-down version the Baillie-PSW test which uses a strong base 2 Fermat probable test combined with a Lucas test with $\Delta$ $=$ $a^2-4$ where minimal $a$ $\ge$ $3$ gives a Jacobi over $n$ as $-1$ and the test $x^{n+1}$ $\equiv$ $1$ $\pmod{n, x^2-ax+1}$ holds.

There is no counterexample to the above tests for $n<2^{64}$