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

DOI:
https://doi.org/10.1090/S0025-5718-02-01424-2

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 ) 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: , and define the base-counting functions:

and

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

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 and passed by an odd composite odd primes) with probability of error . We give explicit formulas to compute , and prove that

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.

**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*, 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*, 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**

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

Email:
zhangzhx@mail.ahwhptt.net.cn

DOI:
https://doi.org/10.1090/S0025-5718-02-01424-2

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