Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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 $\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 [Enhancements On Off] (What's this?)

Similar Articles

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

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