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?)

  • 1. W.R.Alford, A.Granville and C.Pomerance, There are infinitely many Carmichael numbers, Annals of Math., 140 (1994), 703-722. MR 95k:11114
  • 2. W.R.Alford, A.Granville and C.Pomerance, On the difficulty of finding reliable witnesses, Algorithmic Number Theory, pp.1-16, Lecture Notes in Computer Science, vol.877, Springer-Verlag, Berlin, 1994. MR 96d:11136
  • 3. F.Arnault, The Rabin-Monier theorem for Lucas pseudoprimes, Math.Comp., 66 (1997), 869-881. MR 97f :11009
  • 4. R.Baillie and Samuel S.Wagstaff,Jr., Lucas pseudoprimes, Math.Comp., 35 (1980), 1391-1417. MR 81j :10005
  • 5. D.M.Bressoud, Factorization and primality testing, Springer-Verlag, New York, 1989. MR 91e:11150
  • 6. H.Cohen, A Course in Computational Algebraic Number Theory, 3., corr. print. Graduate Texts in Mathematics 138, Springer-Verlag, Berlin, 1996. MR 94i:11105 (1st ed.)
  • 7. H.Cohen and A.K.Lenstra, Implementation of a new primality test, Math.Comp., 48 (1987), 103-121. MR 88c:11080
  • 8. H.Cohen and H.W.Lenstra, Jr., Primality testing and Jacobi sums, Math.Comp., 42 (1984), 297-330. MR 86g:11078
  • 9. J. Grantham, A probable prime test with high confidence, J. Number Theory, 72 (1998), 32-47.MR 2000e:11160
  • 10. J. Grantham, Frobenius Pseudoprimes, Math.Comp., 70 (2001), 873-891. MR 2001g:11191
  • 11. R. K. Guy, Unsolved Problems in Number Theory, Second Edition, Springer-Verlag, New York, 1994. MR 96e:11002
  • 12. L.K.Hua, An introduction to number theory, Springer-Verlag, New York, 1982. MR 83f:10001
  • 13. D.E.Knuth, The art of computer programming : Semi-numerical algorithms,, Volume 2, 2nd ed., Addison Wesley, Reading Massachusetts, 1981. MR 83i:68003
  • 14. H.W.Lenstra, Jr., Primality testing, Computational Methods in Number Theory (H.W. Lenstra, Jr. and R.Tijdeman, eds.), Part I, Math. Centre Tract, vol.154, Amsterdam, 1982, pp.55-77. MR 85g:11117
  • 15. G.Miller, Riemann's hypothesis and tests for primality, J. Comput. and System Sci., 13 (1976),300-317. MR 58:470ab
  • 16. Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoretical Computer Science, 12 (1980), 97-108. MR 82a:68078
  • 17. R.G.E.Pinch, The Carmichael numbers up to $10^{15}$, Math.Comp., 61 (1993), 381-389. MR 93m:11137
  • 18. C.Pomerance, Are there counter-examples to the Baillie-PSW primality test?, Dopo Le Parole aangeboden aan Dr. A.K. Lenstra (H.W.Lenstra, Jr., J.K.Lenstraand P.Van Emde Boas, eds.), Amsterdam,1984.
  • 19. C.Pomerance, J.L.Selfridge and Samuel S.Wagstaff,Jr., The pseudoprimes to $25\cdot10^9$, Math.Comp., 35 (1980), 1003-1026. MR 82g:10030
  • 20. M.O.Rabin, The probabilistic algorithms for testing primality, J.Number Theory, 12 (1980), 128-138. MR 81f :10003
  • 21. K.H.Rosen, Elementary number theory and its applications, Addison Wesley, Reading Massachusetts, 1984. MR 85m:11002
  • 22. H.C.Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), 133-143. MR 56:5414
  • 23. Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math.Comp., 70 (2001), 863-872. MR 2001g:11009
  • 24. Zhenxiang Zhang, Using Lucas sequences to factor large integers near group orders, The Fibonacci Quarterly, 39 (2001), 228-237. MR 2002c:11173

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

American Mathematical Society