[Zhang 2005] Finding C3 -strong pseudoprimes, Mathematics of Computation, 74:250 (2005), 1009-1024.

ABSTRACT.  Let   q1 < q2 < q3   be odd primes and N = q1 q2 q3. Put

d = gcd(q11, q21, q31) and hi = (qi1)/d, i=1, 2, 3.

Then we call d the kernel, the triple (h1, h2, h3) the signature, and H = h1h2h3 the height of N,  respectively. We call N a  C3-number if it is a Carmichael number with each prime factor qi 3 mod 4. If  N is a  C3-number and a strong pseudoprime to the t  bases bi for  1 i t, we call N a  C3-spsp(b1, b2, ,  bt)  . Since  C3-numbers have probability of error 1/4  (the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of ψm (the smallest strong pseudoprime to all the first m  prime bases). If we know the exact value of ψm , we will have, for integers n < ψm, a deterministic efficient primality testing algorithm which is easy to implement.

In this paper, we first describe an algorithm for finding  C3-spsp(2)'s, to a given limit, with heights bounded. There are in total   21978  C3-spsp(2) 's  with heights < 109 . We then give an overview of the 21978  C3-spsp(2)'s and tabulate 54 of them, which are  C3-spsp's to the first 8 prime bases up to  19; three numbers are spsp's to the first 11 prime bases up to 31. No  C3-spsp's  to the first  12 prime bases with heights <109   were found. We conjecture that there exist no  C3-spsp's  to the first 12 prime bases with heights  ≥ 109 and so that

ψ12  =3186 65857 83403 11511 67461 (24 digits)

= 399165290221  ·  798330580441

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those  21978  C3-spsp(2)'s  is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates N = q1 q2 q3 of  C3-spsp(2) 's and their prime factors q1, q2, q3 to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger  C3-spsp's, say up to 1050, with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding  -strong pseudoprimes to the first several prime bases are given.