Finding $C_3$-strong pseudoprimes
HTML articles powered by AMS MathViewer
- by Zhenxiang Zhang PDF
- Math. Comp. 74 (2005), 1009-1024 Request permission
Abstract:
Let $q_1<q_2<q_3$ be odd primes and $N=q_1q_2q_3$. Put \[ d=\gcd (q_1-1,q_2-1,q_3-1) \text { and } h_i=\tfrac {q_i-1}d, \;i=1,2,3. \] 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{equation*} \begin {split} \psi _{12}&= 3186\; 65857\; 83403\; 11511\; 67461\; \text {(24 digits)} \\ &=399165290221\cdot 798330580441, \end{split}\end{equation*} 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
- W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874, DOI 10.2307/2118576
- François Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Comput. 20 (1995), no. 2, 151–161. MR 1374228, DOI 10.1006/jsco.1995.1042
- D. Bleichenbacher, Efficiency and Security of Cryptosystems Based on Number Theory, ETH Ph. D. dissertation 11404, Swiss Federal Institute of Technology, Zurich (1996).
- Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
- Ivan Damgård, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), no. 203, 177–194. MR 1189518, DOI 10.1090/S0025-5718-1993-1189518-9
- Gerhard Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), no. 204, 915–926. MR 1192971, DOI 10.1090/S0025-5718-1993-1192971-8
- Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- R. G. E. Pinch, AllCarmichaelnumberswiththreeprimefactorsupto$10^{18}$, http://www.chalcedon.demon.co.uk/carpsp.html.
- Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
- Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), no. 234, 863–872. MR 1697654, DOI 10.1090/S0025-5718-00-01215-1
- Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Math. Comp. 72 (2003), no. 244, 2085–2097. MR 1986825, DOI 10.1090/S0025-5718-03-01545-X
Additional Information
- Zhenxiang Zhang
- Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China
- Email: zhangzhx@mail.ahwhptt.net.cn
- 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.
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp. 74 (2005), 1009-1024
- MSC (2000): Primary 11Y11, 11A15, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-04-01693-X
- MathSciNet review: 2114662