Finding strong pseudoprimes to several bases
Zhenxiang Zhang · Mathematics of Computation · 2000
Define ψ m \psi _m to be the smallest strong pseudoprime to all the first m m prime bases. If we know the exact value of ψ m \psi _m , we will have, for integers n > ψ m 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, ψ m \psi _m are known for 1 ≤ m ≤ 8 1 \leq m \leq 8 . Upper bounds for ψ 9 , ψ 10 and ψ 11 \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 n>10^{24} to the first ten prime bases 2 , 3 , ⋯ , 29 , 2, 3, \cdots , 29, which have the form n = p q n=p\,q with p , q p, q