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


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

bd   1  mod  n 


bd˙2^r1  mod  n  for some r = 0, 1, … , s1 ,

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,,ψ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 ψ’t  for  13  t  19; to give a lower bound of ψ’20 :  ψ’20 > 1036; and to give reasons and numerical evidence of K2- and  C3-spsp's  to support the following conjecture:  ψt  = ψ’t  < ψ’’t   for any  t  ≥ 12, where  ψ’t  (resp.  ψ’’t  ) is the smallest K2- (resp. C3 -) 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  C3-spsp is an spsp and a Carmichael number of the form: n = q1 q2 q3   with each prime factor qi 3 mod 4.)