Two kinds of strong pseudoprimes up to $10^{36}$

Let $n>1$ be an odd composite integer. Write $n-1=2^sd$ with $d$ odd. If either $b^d \equiv 1$ mod $n$ or $b^{2^rd}\equiv -1$ mod $n$ for some $r=0, 1, \dots, s-1$, then we say that $n$ is a strong pseudoprime to base $b$, or spsp($b$) for short. Define $\psi_t$ to be the smallest strong pseudoprime to all the first $t$ prime bases. If we know the exact value of $\psi_t$, we will have, for integers $n<\psi_t$, a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the $\psi_t$ are known for $1 \leq t \leq 8$. Conjectured values of $\psi_9,\dots,\psi_{12}$ 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 $\psi_t'$ for $13\leq t\leq 19$; to give a lower bound of $\psi_{20}'$: $\psi_{20}'>10^{36}$; and to give reasons and numerical evidence of K2- and $C_3$-spsp's $<10^{36}$ to support the following conjecture: $\psi_t=\psi_t'<\psi_t''$ for any $t\geq 12$, where $\psi_t'$ (resp. $\psi_t''$) is the smallest K2- (resp. $C_3$-) 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 $<10^{36}$ 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_3$-spsp is an spsp and a Carmichael number of the form: $n=q_1q_2q_3$ with each prime factor $q_i\equiv 3$ mod $4$.)