References: [ Home | Author index | Key index | Search ]

Zhang2000

Z. Zhang, "Finding strong pseudoprimes to several bases," Math. Comp., 70:234 (2001) 863--872.  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 ψ₉,ψ₁₀ and ψ₁₁ were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp's) n<10²⁴ to the first ten prime bases 2, 3, ^..., 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 ψ₁₀ 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 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.