Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Author: Zhenxiang Zhang
Journal: Math. Comp. 71 (2002), 1699-1734
MSC (2000): Primary 11Y11; Secondary 11A51, 11R11
Published electronically: May 16, 2002
MathSciNet review: 1933051
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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{displaymath}\text{B}(n)=\char93 \{u: 0\leq u<n,\; n \text{ is a psp}(T_u)\} \end{displaymath}


\begin{displaymath}\text{SB}(n)=\char93 \{u: 0\leq u<n,\; n \text{ is an spsp}(T_u)\}.\end{displaymath}

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

\begin{displaymath}\text{ B}(n)<n/2\; \text{ and$\;$\space SB}(n)<n/8, \end{displaymath}

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{displaymath}\tau(n)< \begin{cases} 1/n^{4/3}, & \text{for $n$\space nons... ... i.e., for $n$\space nonsquare free with } s\geq 2. \end{cases}\end{displaymath}

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11A51, 11R11

Retrieve articles in all journals with MSC (2000): 11Y11, 11A51, 11R11

Additional Information

Zhenxiang Zhang
Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, P. R. China

Keywords: Baillie-PSW probable prime test, Rabin-Miller test, Lucas test, probability of error, (strong) (Lucas) pseudoprimes, quadratic integers, base-counting functions, finite groups (fields), Chinese Remainder Theorem.
Received by editor(s): August 14, 2000
Published electronically: May 16, 2002
Additional Notes: Supported by the China State Educational Commission Science Foundation, the NSF of China Grant 10071001, the SF of Anhui Province Grant 01046103, and the SF of the Education Department of Anhui Province Grant 2002KJ131
Article copyright: © Copyright 2002 American Mathematical Society