Finding Carmichael Numbers Which Are Strong Pseudoprimes

(Department of Mathematics, Anhui Normal University, Wuhu 241000)Abstract: Define ψ_m to be the smallest strong pseudoprimes to all the first m prime bases. If we know the exact value of ψ_m, we will have, for integers < ψ_m, a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi Sum test, the elliptic curve test, or the AKS algorithm. Thanks to Pomer-ance et al. [Math. Comp. Vol.35, 1980, pp.1003-1026; MR 82g:10030] and Jaeschke [Math. Comp. Vol.61, 1993, pp.915-926; MR 94d:11004], ψ_m are known for 1 ≤ m ≤ 8. Zhang and Tang [Math. Comp. Vol.72, 2003, pp.2085-2097; MR 2004c:11008] used a fast algorithm to find all C₃-numbers < 10²⁰ which are also strong pseudoprimes to the first 5 prime bases. Here C₃-numbers mean Carmichael numbers N = q1q2q3 with 3 prime factors q1 = q2 = q3 = 3 mod 4. (Such numbers have a high probability to be strong pseudoprimes to more bases.) They gave a conjected value for ψ₉, ψ₁₀ and ψ₁₁:ψ₉ = ψ₁₀ = ψ₁₁ = 3825 12305 65464 13051 = 149491 ? 747451 ? 34233211,and gave reasons to support the conjecture. Not long later, Zhang [Math. Comp. Vol.74, 2005, pp.1009-1024; MR 2114662 (2005k:11243)] used another new method to find almost all C₃-numbers < 10²⁴, which are also strong pseudoprime to the first 9 prime bases. He gave a conjected valu of ψ₁₂:ψ₁₂ = 3186 65857 83403 11511 67461 = 399165290221 ? 798330580441,and gave reasons to support the conjecture.In this paper we enlighted by the work of Zhang, correspondingly define C_3,1-numbers and C_3,2 -numbers to be Carmichael numbers N = 919293 with 3 prime factors q1 = q2 = q3 = 5 mod 8; and q1 = q2 = 3 mod 4,q3 = 9 mod 16 respectively. (Such numbers also have a high probability to be strong pseudoprimes, only lower than C₃-numbers of 3-factors Carmichael numbers.) We first give sufficient and necessary conditions for such numbers; then give algorithms for finding such numbers. We find all C_3,1-numbers < 10²⁴ which are strong pseudoprmes to 2, there are 55971 numbers in total, only 1 of them is a strong pseudoprmes to the first 8 prime bases; no C_3,1-strong pseudoprmes to the first 9 prime bases are found. We also find all C_3,2-numbers < 10²⁴ which are strong pseudoprmes to 2, there are 11327 numbers in total, only 1 of them is a strong pseudoprme to the first 5 prime bases; no C_3,2 -strong pseudoprmes to the first 6 prime bases are found. These data enhence the reliability of the conjectured values of ψ₉, ψ₁₀, ψ₁₁ and ψ₁₂ given by Zhang.