Finding strong pseudoprimes
Author:
Zhenxiang Zhang
Journal:
Math. Comp. 74 (2005), 10091024
MSC (2000):
Primary 11Y11, 11A15, 11A51.
Published electronically:
November 2, 2004
MathSciNet review:
2114662
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be odd primes and . Put
Then we call the kernel, the triple the signature, and the height of , respectively. We call a number if it is a Carmichael number with each prime factor . If is a number and a strong pseudoprime to the bases for , we call a spsp . Since numbers have probability of error (the upper bound of that for the RabinMiller test), they often serve as the exact values or upper bounds of (the smallest strong pseudoprime to all the first prime bases). If we know the exact value of , we will have, for integers , a deterministic efficient primality testing algorithm which is easy to implement. In this paper, we first describe an algorithm for finding spsp(2)'s, to a given limit, with heights bounded. There are in total spsp's with heights . We then give an overview of the 21978  spsp(2)'s and tabulate of them, which are spsp's to the first prime bases up to ; three numbers are spsp's to the first 11 prime bases up to 31. No spsp's to the first prime bases with heights were found. We conjecture that there exist no spsp's to the first prime bases with heights and so that
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 spsp's is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates of spsp's and their prime factors to Miller's tests, and obtain the desired numbers. At last we speed our algorithm for finding larger spsp's, say up to , with a given signature to more prime bases. Comparisons of effectiveness with Arnault's and our previous methods for finding strong pseudoprimes to the first several prime bases are given.
 1.
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
(95k:11114), http://dx.doi.org/10.2307/2118576
 2.
François
Arnault, Constructing Carmichael numbers which are strong
pseudoprimes to several bases, J. Symbolic Comput. 20
(1995), no. 2, 151–161. MR 1374228
(96k:11153), http://dx.doi.org/10.1006/jsco.1995.1042
 3.
D. Bleichenbacher, Efficiency and Security of Cryptosystems Based on Number Theory, ETH Ph. D. dissertation 11404, Swiss Federal Institute of Technology, Zurich (1996).
 4.
Richard
Crandall and Carl
Pomerance, Prime numbers, SpringerVerlag, New York, 2001. A
computational perspective. MR 1821158
(2002a:11007)
 5.
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
(94b:11124), http://dx.doi.org/10.1090/S00255718199311895189
 6.
Gerhard
Jaeschke, On strong pseudoprimes to several
bases, Math. Comp. 61
(1993), no. 204, 915–926. MR 1192971
(94d:11004), http://dx.doi.org/10.1090/S00255718199311929718
 7.
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 8.
R. G. E. Pinch, All Carmichael numbers with three prime factors up to , http://www. chalcedon.demon.co.uk/carpsp.html.
 9.
Carl
Pomerance, J.
L. Selfridge, and Samuel
S. Wagstaff Jr., The pseudoprimes to
25⋅10⁹, Math. Comp.
35 (1980), no. 151, 1003–1026. MR 572872
(82g:10030), http://dx.doi.org/10.1090/S00255718198005728727
 10.
Michael
O. Rabin, Probabilistic algorithm for testing primality, J.
Number Theory 12 (1980), no. 1, 128–138. MR 566880
(81f:10003), http://dx.doi.org/10.1016/0022314X(80)900840
 11.
Zhenxiang
Zhang, Finding strong pseudoprimes to several
bases, Math. Comp. 70
(2001), no. 234, 863–872. MR 1697654
(2001g:11009), http://dx.doi.org/10.1090/S0025571800012151
 12.
Zhenxiang
Zhang and Min
Tang, Finding strong pseudoprimes to several
bases. II, Math. Comp. 72
(2003), no. 244, 2085–2097
(electronic). MR
1986825 (2004c:11008), http://dx.doi.org/10.1090/S002557180301545X
 1.
 W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Annals of Math. 140 (1994), 703722. MR 95k:11114
 2.
 F. Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Computation 20 (1995), 151161. MR 96k:11153
 3.
 D. Bleichenbacher, Efficiency and Security of Cryptosystems Based on Number Theory, ETH Ph. D. dissertation 11404, Swiss Federal Institute of Technology, Zurich (1996).
 4.
 R. Crandall and C. Pomerance, Prime numbers, a computational perspective, SpringerVerlag, New York, 2001. MR 2002a:11007
 5.
 I. Damgård, P. Landrock, and C. Pomerance, Average case estimates for the strong probable prime test, Math. Comp. 61 (1993), 177194. MR 94b:11124
 6.
 G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), 915926. MR 94d:11004
 7.
 G. Miller, Riemann's hypothesis and tests for primality, J. Comput. and System Sci. 13 (1976), 300317. MR 58:470a
 8.
 R. G. E. Pinch, All Carmichael numbers with three prime factors up to , http://www. chalcedon.demon.co.uk/carpsp.html.
 9.
 C. Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The pseudoprimes to , Math. Comp. 35 (1980), 10031026. MR 82g:10030
 10.
 M. O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128138. MR 81f:10003
 11.
 Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), 863872. http://www.ams.org/journalgetitem?pii=S0025571800012151 MR 2001g:11009
 12.
 Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Math. Comp. 72 (2003), 20852097. http://www.ams.org/journalgetitem?pii=S0025571803 01545X MR 2004c:11008
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
Email:
zhangzhx@mail.ahwhptt.net.cn
DOI:
http://dx.doi.org/10.1090/S002557180401693X
PII:
S 00255718(04)01693X
Keywords:
Carmichael numbers,
$C_3$numbers,
strong pseudoprimes,
$C_3$spsp's,
RabinMiller 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
