Finding strong pseudoprimes to several bases

Author:
Zhenxiang Zhang

Journal:
Math. Comp. **70** (2001), 863-872

MSC (2000):
Primary 11Y11, 11A15, 11A51

Published electronically:
February 17, 2000

MathSciNet review:
1697654

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Define to be the smallest strong pseudoprime to all the first prime bases. If we know the exact value of , we will have, for integers , a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, are known for . Upper bounds for were given by Jaeschke.

In this paper we tabulate all strong pseudoprimes (spsp's) to the first ten prime bases which have the form with odd primes and There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp's to both bases 31 and 37. As a result the upper bounds for and are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke's and Arnault's methods are given.

**1.**Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely,*On distinguishing prime numbers from composite numbers*, Ann. of Math. (2)**117**(1983), no. 1, 173–206. MR**683806**, 10.2307/2006975**2.**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**3.**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**4.**F. Arnault,*Rabin-Miller primality test: composite numbers which pass it*, Math. Comp.**64**(1995), no. 209, 355–361. MR**1260124**, 10.1090/S0025-5718-1995-1260124-2**5.**A. O. L. Atkin and F. Morain,*Elliptic curves and primality proving*, Math. Comp.**61**(1993), no. 203, 29–68. MR**1199989**, 10.1090/S0025-5718-1993-1199989-X**6.**W.Bosma and M.P. van der Hulst,*Primality proving with cyclotomy*, thesis, Univ. of Amsterdam, 1990.**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.**David A. Cox,*Primes of the form 𝑥²+𝑛𝑦²*, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR**1028322****10.**Kenneth F. Ireland and Michael I. Rosen,*A classical introduction to modern number theory*, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR**661047****11.**Gerhard Jaeschke,*On strong pseudoprimes to several bases*, Math. Comp.**61**(1993), no. 204, 915–926. MR**1192971**, 10.1090/S0025-5718-1993-1192971-8**12.**Gary L. Miller,*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295****13.**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**14.**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**15.**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

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

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

Additional Information

**Zhenxiang Zhang**

Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, P. R. China;
State Key Laboratory of Information Security, Graduate School USTC, 100039 Beijing, P. R. China

Email:
zhangzhx@mail.ahwhptt.net.cn

DOI:
https://doi.org/10.1090/S0025-5718-00-01215-1

Keywords:
Strong pseudoprimes,
Rabin-Miller test,
biquadratic residue characters,
cubic residue characters,
Chinese remainder theorem

Received by editor(s):
August 1, 1997

Received by editor(s) in revised form:
June 22, 1998, and May 24, 1999

Published electronically:
February 17, 2000

Additional Notes:
Supported by the China State Educational Commission Science Foundation and by NSF of China Grant 10071001.

Dedicated:
Dedicated to the memory of P. Erdős (1913–1996)

Article copyright:
© Copyright 2000
American Mathematical Society