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

Abstract:

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$.)