[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(q1−1, q2−1, q3−1) and hi = (qi−1)/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
= 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.