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 $(D/n)=-1$) 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: $T_u=T \mod (T^2-uT+1)$, and define the base-counting functions:

and

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

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 $\geq 5$and passed by an odd composite $n=p_1^{r_1}p_2^{r_2}\cdots p_s^{r_s}\;(p_1<p_2<\cdots<p_s$ odd primes) with probability of error $\tau(n)$. We give explicit formulas to compute $\tau(n)$, 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.