A one-parameter quadratic-base version of the Baillie-PSW probable prime test

The well-known Baillie-PSW probable prime test is a combination of a Rabin-Miller test and a ``true' (i.e., with ) Lucas test. Arnault mentioned in a recent paper that no precise result is known about its probability of error. Grantham recently provided a probable prime test (RQFT) with probability of error less than 1/7710, and pointed out that the lack of counter-examples to the Baillie-PSW test indicates that the true probability of error may be much lower.

In this paper we first define pseudoprimes and strong pseudoprimes to quadratic bases with one parameter: , and define the base-counting functions:

and

Then we give explicit formulas to compute B and SB, and prove that, for odd composites ,

and point out that these are best possible. Finally, based on one-parameter quadratic-base pseudoprimes, we provide a probable prime test, called the One-Parameter Quadratic-Base Test (OPQBT), which passed by all primes and passed by an odd composite odd primes) with probability of error . We give explicit formulas to compute , and prove that

The running time of the OPQBT is asymptotically 4 times that of a Rabin-Miller test for worst cases, but twice that of a Rabin-Miller test for most composites. We point out that the OPQBT has clear finite group (field) structure and nice symmetry, and is indeed a more general and strict version of the Baillie-PSW test. Comparisons with Gantham's RQFT are given.