Two kinds of strong pseudoprimes up to $10^{36}$
HTML articles powered by AMS MathViewer
- by Zhenxiang Zhang PDF
- Math. Comp. 76 (2007), 2095-2107 Request permission
Abstract:
Let $n>1$ be an odd composite integer. Write $n-1=2^sd$ with $d$ odd. If either $b^d \equiv 1$ mod $n$ or $b^{2^rd}\equiv -1$ mod $n$ for some $r=0, 1, \dots , s-1$, then we say that $n$ is a strong pseudoprime to base $b$, or spsp($b$) for short. Define $\psi _t$ to be the smallest strong pseudoprime to all the first $t$ prime bases. If we know the exact value of $\psi _t$, we will have, for integers $n<\psi _t$, a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the $\psi _t$ are known for $1 \leq t \leq 8$. Conjectured values of $\psi _9,\dots ,\psi _{12}$ were given by us in our previous papers (Math. Comp. 72 (2003), 2085–2097; 74 (2005), 1009–1024). The main purpose of this paper is to give exact values of $\psi _t’$ for $13\leq t\leq 19$; to give a lower bound of $\psi _{20}’$: $\psi _{20}’>10^{36}$; and to give reasons and numerical evidence of K2- and $C_3$-spsp’s $<10^{36}$ to support the following conjecture: $\psi _t=\psi _t’<\psi _t”$ for any $t\geq 12$, where $\psi _t’$ (resp. $\psi _t”$) is the smallest K2- (resp. $C_3$-) strong pseudoprime to all the first $t$ prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp’s $<10^{36}$ to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/1.8GHz. (Recall that a K2-spsp is an spsp of the form: $n=pq$ with $p,q$ primes and $q-1=2(p-1)$; and that a $C_3$-spsp is an spsp and a Carmichael number of the form: $n=q_1q_2q_3$ with each prime factor $q_i\equiv 3$ mod $4$.)References
- Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
- 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
- Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
- 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
- Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, DOI 10.1016/0304-3975(80)90007-9
- 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, Finding $C_3$-strong pseudoprimes, Math. Comp. 74 (2005), no. 250, 1009–1024. MR 2114662, DOI 10.1090/S0025-5718-04-01693-X
- 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, People’s Republic of China
- Email: zhangzhx@mail.wh.ah.cn, ahnu_zzx@sina.com
- Received by editor(s): March 8, 2006
- Received by editor(s) in revised form: July 8, 2006
- Published electronically: April 17, 2007
- Additional Notes: The author was supported by the NSF of China Grant 10071001
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 76 (2007), 2095-2107
- MSC (2000): Primary 11Y11, 11A15, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-07-01977-1
- MathSciNet review: 2336285
Dedicated: Dedicated to the memory of Kencheng Zeng (1927–2004)