Finding strong pseudoprimes to several bases. II
HTML articles powered by AMS MathViewer
- by Zhenxiang Zhang and Min Tang PDF
- Math. Comp. 72 (2003), 2085-2097 Request permission
Abstract:
Define $\psi _m$ to be 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. Thanks to Pomerance et al. and Jaeschke, the $\psi _m$ are known for $1 \leq m \leq 8$. Upper bounds for $\psi _9,\psi _{10} \text { and } \psi _{11}$ were first given by Jaeschke, and those for $\psi _{10} \text { and } \psi _{11}$ were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863–872). In this paper, we first follow the first author’s previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp’s) $n<10^{24}$ to the first five or six prime bases, which have the form $n=p q$ with $p, q$ odd primes and $q-1=k(p-1), k=4/3, 5/2, 3/2, 6$; then we tabulate all Carmichael numbers $<10^{20}$, to the first six prime bases up to 13, which have the form $n=q_1q_2q_3$ with each prime factor $q_i\equiv 3\mod 4$. There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp’s to base 17; 5 numbers are spsp’s to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for $\psi _{9}, \psi _{10}$ and $\psi _{11}$ are lowered from 20- and 22-decimal-digit numbers to a 19-decimal-digit number: \begin{equation*} \begin {split} \psi _{9}\leq \psi _{10}\leq \psi _{11}\leq Q_{11} &=3825\;12305\;65464\;13051\;\text { (19 digits)}\\ &= 149491\cdot 747451\cdot 34233211. \end{split} \end{equation*} We conjecture that \[ \psi _{9}= \psi _{10}= \psi _{11}=3825\;12305\;65464\;13051,\] and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor $q_3$ and propose necessary conditions on $n$ to be a strong pseudoprime to the first $5$ prime bases. Comparisons of effectiveness with Arnault’s, Bleichenbacher’s, Jaeschke’s, and Pinch’s methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.References
- W. R. Alford, Andrew Granville, and Carl Pomerance, On the difficulty of finding reliable witnesses, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 1–16. MR 1322705, DOI 10.1007/3-540-58691-1_{3}6
- 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).
- 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
- Kenneth F. Ireland and Michael I. Rosen, A classical introduction to modern number theory, Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York-Berlin, 1982. Revised edition of Elements of number theory. MR 661047
- 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
- R. G. E. Pinch, The Carmichael numbers up to $10^{15}$, Math. Comp. 61 (1993), no. 203, 381–391. MR 1202611, DOI 10.1090/S0025-5718-1993-1202611-7
- —, All Carmichael numbers with three prime factors up to $10^{18}$, http://www.chalcedon.demon.co.uk/carpsp.html.
- J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI 10.1007/bf01933667
- 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, Using Lucas sequences to factor large integers near group orders, Fibonacci Quart. 39 (2001), no. 3, 228–237. MR 1840030
- Zhenxiang Zhang, A one-parameter quadratic-base version of the Baillie-PSW probable prime test, Math. Comp. 71 (2002), no. 240, 1699–1734. MR 1933051, DOI 10.1090/S0025-5718-02-01424-2
Additional Information
- Zhenxiang Zhang
- Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China
- Email: zhangzhx@mail.ahwhptt.net.cn
- Min Tang
- Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China
- Received by editor(s): July 9, 2001
- Published electronically: May 30, 2003
- 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 2003 American Mathematical Society
- Journal: Math. Comp. 72 (2003), 2085-2097
- MSC (2000): Primary 11Y11, 11A15, 11A51
- DOI: https://doi.org/10.1090/S0025-5718-03-01545-X
- MathSciNet review: 1986825