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 ) 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, Andrew Granville, and Carl Pomerance,*There are infinitely many Carmichael numbers*, Ann. of Math. (2)**139**(1994), no. 3, 703–722. MR**1283874**, 10.2307/2118576**2.**W. R. Alford, Andrew Granville, and Carl Pomerance,*On the difficulty of finding reliable witnesses*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 1–16. MR**1322705**, 10.1007/3-540-58691-1_36**3.**F. Arnault,*The Rabin-Monier theorem for Lucas pseudoprimes*, Math. Comp.**66**(1997), no. 218, 869–881. MR**1408370**, 10.1090/S0025-5718-97-00836-3**4.**Robert Baillie and Samuel S. Wagstaff Jr.,*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, 10.1090/S0025-5718-1980-0583518-6**5.**David M. Bressoud,*Factorization and primality testing*, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1989. MR**1016812****6.**Henri Cohen,*A course in computational algebraic number theory*, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206****7.**H. Cohen and A. K. Lenstra,*Implementation of a new primality test*, Math. Comp.**48**(1987), no. 177, 103–121, S1–S4. MR**866102**, 10.1090/S0025-5718-1987-0866102-2**8.**H. Cohen and H. W. Lenstra Jr.,*Primality testing and Jacobi sums*, Math. Comp.**42**(1984), no. 165, 297–330. MR**726006**, 10.1090/S0025-5718-1984-0726006-X**9.**Jon Grantham,*A probable prime test with high confidence*, J. Number Theory**72**(1998), no. 1, 32–47. MR**1643284**, 10.1006/jnth.1998.2247**10.**Jon Grantham,*Frobenius pseudoprimes*, Math. Comp.**70**(2001), no. 234, 873–891. MR**1680879**, 10.1090/S0025-5718-00-01197-2**11.**Richard K. Guy,*Unsolved problems in number theory*, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR**1299330****12.**Loo Keng Hua,*Introduction to number theory*, Springer-Verlag, Berlin-New York, 1982. Translated from the Chinese by Peter Shiu. MR**665428****13.**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****14.**H. W. Lenstra Jr.,*Primality testing*, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 55–77. MR**700258****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*, Theoret. Comput. Sci.**12**(1980), no. 1, 97–108. MR**582244**, 10.1016/0304-3975(80)90007-9**17.**R. G. E. Pinch,*The Carmichael numbers up to 10¹⁵*, Math. Comp.**61**(1993), no. 203, 381–391. MR**1202611**, 10.1090/S0025-5718-1993-1202611-7**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.**Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,*The pseudoprimes to 25⋅10⁹*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, 10.1090/S0025-5718-1980-0572872-7**20.**Michael O. Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, 10.1016/0022-314X(80)90084-0**21.**Kenneth H. Rosen,*Elementary number theory and its applications*, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1984. MR**755333****22.**H. C. Williams,*On numbers analogous to the Carmichael numbers*, Canad. Math. Bull.**20**(1977), no. 1, 133–143. MR**0447099****23.**Zhenxiang Zhang,*Finding strong pseudoprimes to several bases*, Math. Comp.**70**(2001), no. 234, 863–872. MR**1697654**, 10.1090/S0025-5718-00-01215-1**24.**Zhenxiang Zhang,*Using Lucas sequences to factor large integers near group orders*, Fibonacci Quart.**39**(2001), no. 3, 228–237. MR**1840030**

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