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

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^2-uT+1)$, and define the base-counting functions: \begin{equation*} \mathrm {B}(n) = \#\{u: 0\leq u<n,\; \text {$n$ is a $\operatorname {psp}(T_u)$}\} \end{equation*} and \begin{equation*} \mathrm {SB}(n) = \#\{u: 0\leq u<n,\; \text {$n$ is an $\operatorname {spsp}(T_u)$}\}. \end{equation*} Then we give explicit formulas to compute B$(n)$ and SB$(n)$, and prove that, for odd composites $n$, \begin{equation*}\text { B}(n)<n/2\; \text { and$\;$ SB}(n)<n/8, \end{equation*} 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 \begin{equation*} \tau (n)< \begin {cases} 1/n^{4/3}, & \text {for $n$ nonsquare free with } s=1; \\ 1/n^{2/3}, & \text {for $n$ square free with } s=2; \\ 1/n^{2/7}, & \text {for $n$ square free with } s=3; \\ \frac {1}{8^{s-4}\cdot 166(p_1+1)}, & \text {for $n$ square free with $s$ even} \geq 4; \\ \frac {1}{16^{s-5}\cdot 119726}, & \text {for $n$ square free with $s$ odd} \geq 5;\\ \frac {1}{4^s}\prod _{i=1}^{s}\frac {1}{p_i^{2(r_i-1)}}, & \text {otherwise, i.e., for $n$ nonsquare free with } s\geq 2. \end{cases} \end{equation*} 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.