[Zhang 2002] A oneparameter quadraticbase
version of the BailliePSW probable prime test,
Mathematics of
Computation,71:240 (2002), 16991734. ABSTRACT:
The wellknown BailliePSW probable prime test is a
combination of a RabinMiller 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 counterexamples to the BailliePSW
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 basecounting functions: B(n) = # {u: 0 _{ }≤ u
< n, n is
a psp(T_{u}) } and
SB(n)
= # {u: 0 _{ }≤ u
< n, n is
an spsp(T_{u}) } Then
we give explicit formulas to compute B(n) and SB(n), and prove that,
for odd composites n, B(n) < n/2 and SB(n)
< n/8, and
point out that these are best possible. Finally, based on oneparameter
quadraticbase pseudoprimes,
we provide a probable prime test, called the OneParameter QuadraticBase
Test (OPQBT), which passed by all primes ≥ 5
and passed by an odd composite n = p_{1}^{r}^{1} p_{2}^{r}^{2}…p_{s}^{r}^{s}^{ } (p_{1}< p_{2}< …<
p_{s} odd
primes) with
probability of errorτ(n). We give
explicit formulas to compute τ(n), and prove that τ(n)
< 1/n^{4/3}, for n nonsquare free with s = 1; τ(n)
< 1/n^{2/3}, for n square free
with s = 2; τ(n)
< 1/n^{2/7}, for n square free with s = 3; τ(n)
< 1/(8^{s4}^{ }· 166(p_{1}+1) ), for n square free with s even ≥ 4; τ(n)
< 1/(16^{s5}^{ }·119726), for n square free with s odd ≥ 5; τ(n) < (1/4^{s})∏_{1≤ }_{i}^{ }_{≤ s} 1/p_{i}^{2(ri} _{ }^{−}_{ }^{1)}, otherwise,
i.e., for n nonsquare free with s ≥ 2. The running time of the OPQBT is asymptotically 4 times
that of a RabinMiller test for worst cases, but twice that of
a RabinMiller 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 BailliePSW test. Comparisons with Gantham's RQFT are given.  
