[Zhang 2002] A one-parameter quadratic-base version of the Baillie-PSW probable prime test,

Mathematics of Computation , 71:240 (2002), 1699-1734.

ABSTRACT: 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²−uT+1),

and define the base-counting 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 one-parameter quadratic-base pseudoprimes, we provide a probable prime test, called the One-Parameter Quadratic-Base Test (OPQBT), which passed by all primes ≥ 5 and passed by an odd composite

n = p₁^r1 p₂^r2…p_s^rs (p₁< p₂< …< 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^s-4 · 166(p₁+1) ), for n square free with s even ≥ 4;

τ(n) < 1/(16^s-5 ·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 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.

---------------------------------------------------------------------------------------------------------------