## Finding strong pseudoprimes to several bases

HTML articles powered by AMS MathViewer

- by Zhenxiang Zhang PDF
- Math. Comp.
**70**(2001), 863-872 Request permission

## Abstract:

Define $\psi _m$ to be the smallest strong pseudoprime to all the first $m$ prime bases. If we know the exact value of $\psi _m$, we will have, for integers $n<\psi _m$, 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, $\psi _m$ are known for $1 \leq m \leq 8$. Upper bounds for $\psi _9,\psi _{10} \text { and } \psi _{11}$ were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp’s) $n<10^{24}$ to the first ten prime bases $2, 3, \cdots , 29,$ which have the form $n=p q$ with $p, q$ odd primes and $q-1=k(p-1), k=2, 3, 4.$ 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 $\psi _{10}$ and $\psi _{11}$ are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for $\psi _{12}$ is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for $n$ 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.## References

- 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**, DOI 10.2307/2006975 - 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**, DOI 10.2307/2118576 - 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**, DOI 10.1007/3-540-58691-1_{3}6 - F. Arnault,
*Rabin-Miller primality test: composite numbers which pass it*, Math. Comp.**64**(1995), no. 209, 355–361. MR**1260124**, DOI 10.1090/S0025-5718-1995-1260124-2 - A. O. L. Atkin and F. Morain,
*Elliptic curves and primality proving*, Math. Comp.**61**(1993), no. 203, 29–68. MR**1199989**, DOI 10.1090/S0025-5718-1993-1199989-X - W.Bosma and M.P. van der Hulst,
*Primality proving with cyclotomy*, thesis, Univ. of Amsterdam, 1990. - H. Cohen and A. K. Lenstra,
*Implementation of a new primality test*, Math. Comp.**48**(1987), no. 177, 103–121, S1–S4. MR**866102**, DOI 10.1090/S0025-5718-1987-0866102-2 - H. Cohen and H. W. Lenstra Jr.,
*Primality testing and Jacobi sums*, Math. Comp.**42**(1984), no. 165, 297–330. MR**726006**, DOI 10.1090/S0025-5718-1984-0726006-X - David A. Cox,
*Primes of the form $x^2 + ny^2$*, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR**1028322** - 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** - Gerhard Jaeschke,
*On strong pseudoprimes to several bases*, Math. Comp.**61**(1993), no. 204, 915–926. MR**1192971**, DOI 10.1090/S0025-5718-1993-1192971-8 - Gary L. Miller,
*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. MR**480295**, DOI 10.1016/S0022-0000(76)80043-8 - Louis Monier,
*Evaluation and comparison of two efficient probabilistic primality testing algorithms*, Theoret. Comput. Sci.**12**(1980), no. 1, 97–108. MR**582244**, DOI 10.1016/0304-3975(80)90007-9 - Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,
*The pseudoprimes to $25\cdot 10^{9}$*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, DOI 10.1090/S0025-5718-1980-0572872-7 - Michael O. Rabin,
*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, DOI 10.1016/0022-314X(80)90084-0

## 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
- 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.
- © Copyright 2000 American Mathematical Society
- Journal: Math. Comp.
**70**(2001), 863-872 - MSC (2000): Primary 11Y11, 11A15, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-00-01215-1
- MathSciNet review: 1697654

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