Home
Search Site
Largest
Finding
How Many?
Mersenne
Glossary
Prime Curios!
email list
FAQ
Prime Lists
Titans
Submit primes

This is the Prime Pages'
interface to our BibTeX database. Rather than being an exhaustive database,
it just lists the references we cite on these pages. Please let me know of any errors you notice.References: [ Home  Author index  Key index  Search ]
 Zhang2000
 Z. Zhang, "Finding strong pseudoprimes to several bases," Math. Comp., 70:234 (2001) 863872. MR 2001g:11009
Abstract:
Define ψ_{m} to be the smallest strong pseudoprime to all the first m prime bases. If we know the exact value of ψ_{m}, we will have, for integers n<ψ_{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, ψ_{m} are known for 1 < m < 8. Upper bounds for ψ_{9},ψ_{10} and ψ_{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, ^{...}, 29, which have the form n=p,q with p, q odd primes and q1=k(p1), 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 ψ_{10} and ψ_{11} are lowered from 28 and 29decimaldigit numbers to 22decimaldigit numbers, and a 24decimaldigit upper bound for ψ_{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.
