[Zhang 2007] Two  kinds of strong pseudoprimes up to 10³⁶, Mathematics of Computation, 76:260 (2007), 2095-2107. 

ABSTRACT. Let n > 1 be an odd composite integer. Write n −1=2^sd , with d odd. If either

b^d ≡ 1 mod n

or

b^d˙^{2^r} ≡ −1 mod n for some r = 0, 1, … , s−1 ,

then we say that n is a strong pseudoprime to base b , or spsp(b) for short. Define ψ_t to be the smallest strong pseudoprime to all the first t prime bases. If we know the exact value of ψ_t , we will have, for integers n < ψ_t , a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the ψ_t are known for 1 ≤ t ≤ 8. Conjectured values of ψ_9,…,ψ₁₂ were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024).

The main purpose of this paper is to give exact values of ψ’_t for 13 ≤ t ≤ 19; to give a lower bound of ψ’₂₀ : ψ’₂₀ > 10³⁶; and to give reasons and numerical evidence of K2- and C₃-spsp's to support the following conjecture: ψ_t = ψ’_t < ψ’’_t for any t ≥ 12, where ψ’_t (resp. ψ’’_t ) is the smallest K2- (resp. C₃ -) strong pseudoprime to all the first t prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: n = pq with p, q primes and q −1 = 2 (p −1) ; and that a C₃-spsp is an spsp and a Carmichael number of the form: n = q₁ q₂ q₃ with each prime factor q_i ≡ 3 mod 4.)