Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Finding $C_3$-strong pseudoprimes

Author: Zhenxiang Zhang
Journal: Math. Comp. 74 (2005), 1009-1024
MSC (2000): Primary 11Y11, 11A15, 11A51.
Published electronically: November 2, 2004
MathSciNet review: 2114662
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $q_1<q_2<q_3$ be odd primes and $N=q_1q_2q_3$. Put

\begin{displaymath}d=\gcd(q_1-1,q_2-1,q_3-1) \text{ and } h_i=\tfrac{q_i-1}d, \;i=1,2,3. \end{displaymath}

Then we call $d$ the kernel, the triple $(h_1,h_2,h_3)$ the signature, and $H=h_1h_2h_3$ the height of $N$, respectively. We call $N$ a $C_3$-number if it is a Carmichael number with each prime factor $q_i\equiv 3\mod 4$. If $N$ is a $C_3$-number and a strong pseudoprime to the $t$ bases $b_i$ for $1\leq i\leq t$, we call $N$ a $C_3$-spsp $(b_1, b_2,\dots,b_t)$. Since $C_3$-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 $\psi_m$ (the smallest strong pseudoprime to all the first $m$ prime bases). If we know the exact value of $\psi_m$, we will have, for integers $n<\psi_m$, a deterministic efficient primality testing algorithm which is easy to implement.

In this paper, we first describe an algorithm for finding $C_3$-spsp(2)'s, to a given limit, with heights bounded. There are in total $21978$ $C_3$-spsp$(2)$'s $<10^{24}$ with heights $<10^9$. We then give an overview of the 21978 $C_3$- spsp(2)'s and tabulate $54$ of them, which are $C_3$-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 $C_3$-spsp's $<10^{24}$ to the first $12$ prime bases with heights $<10^9$ were found. We conjecture that there exist no $C_3$-spsp's $<10^{24}$to the first $12$ prime bases with heights $\geq 10^9$ and so that

\begin{displaymath}\begin{split} \psi_{12}&= 3186\; 65857\; 83403\; 11511\; 6746... ...{(24 digits)}\\ &=399165290221\cdot 798330580441, \end{split}\end{displaymath}

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$ $C_3$-spsp$(2)$'s is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates $N=q_1q_2q_3$ of $C_3$-spsp$(2)$'s and their prime factors $q_1,q_2,q_3$ to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger $C_3$-spsp's, say up to $10^{50}$, with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding $C_3$-strong pseudoprimes to the first several prime bases are given.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11A15, 11A51.

Retrieve articles in all journals with MSC (2000): 11Y11, 11A15, 11A51.

Additional Information

Zhenxiang Zhang
Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China

Keywords: Carmichael numbers, $C_3$-numbers, strong pseudoprimes, $C_3$-spsp's, Rabin-Miller test, Chinese Remainder Theorem.
Received by editor(s): August 16, 2003
Received by editor(s) in revised form: January 8, 2004
Published electronically: November 2, 2004
Additional Notes: Supported by the NSF of China Grant 10071001, the SF of Anhui Province Grant 01046103, and the SF of the Education Department of Anhui Province Grant 2002KJ131.
Article copyright: © Copyright 2004 American Mathematical Society