Finding strong pseudoprimes to several bases. II
Authors:
Zhenxiang Zhang and Min Tang
Journal:
Math. Comp. 72 (2003), 20852097
MSC (2000):
Primary 11Y11, 11A15, 11A51
Published electronically:
May 30, 2003
MathSciNet review:
1986825
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Define to be 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. Thanks to Pomerance et al. and Jaeschke, the are known for . Upper bounds for were first given by Jaeschke, and those for were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863872). 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) to the first five or six prime bases, which have the form with odd primes and ; then we tabulate all Carmichael numbers , to the first six prime bases up to 13, which have the form with each prime factor . 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 and are lowered from 20 and 22decimaldigit numbers to a 19decimaldigit number:
We conjecture that and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor and propose necessary conditions on to be a strong pseudoprime to the first 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.
 1.
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
(96d:11136), http://dx.doi.org/10.1007/3540586911_36
 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.
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
 5.
Kenneth
F. Ireland and Michael
I. Rosen, A classical introduction to modern number theory,
Graduate Texts in Mathematics, vol. 84, SpringerVerlag, New
YorkBerlin, 1982. Revised edition of Elements of number theory. MR 661047
(83g:12001)
 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.
Louis
Monier, Evaluation and comparison of two efficient probabilistic
primality testing algorithms, Theoret. Comput. Sci.
12 (1980), no. 1, 97–108. MR 582244
(82a:68078), http://dx.doi.org/10.1016/03043975(80)900079
 9.
R.
G. E. Pinch, The Carmichael numbers up to
10¹⁵, Math. Comp.
61 (1993), no. 203, 381–391. MR 1202611
(93m:11137), http://dx.doi.org/10.1090/S00255718199312026117
 10.
, All Carmichael numbers with three prime factors up to , http://www.chalcedon.demon.co.uk/carpsp.html.
 11.
J.
M. Pollard, A Monte Carlo method for factorization, Nordisk
Tidskr. Informationsbehandling (BIT) 15 (1975),
no. 3, 331–334. MR 0392798
(52 #13611)
 12.
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
 13.
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
 14.
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
 15.
Zhenxiang
Zhang, Using Lucas sequences to factor large integers near group
orders, Fibonacci Quart. 39 (2001), no. 3,
228–237. MR 1840030
(2002c:11173)
 16.
Zhenxiang
Zhang, A oneparameter quadraticbase version
of the BailliePSW probable prime test, Math.
Comp. 71 (2002), no. 240, 1699–1734 (electronic). MR 1933051
(2003f:11191), http://dx.doi.org/10.1090/S0025571802014242
 1.
 W. R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses, Algorithmic Number Theory, pp. 116, Lecture Notes in Computer Science, vol. 877, SpringerVerlag, Berlin, 1994. MR 96d:11136
 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.
 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
 5.
 K. Ireland and M. Rosen, A classical introduction to modern number theory, SpringerVerlag, New York, 1982. MR 83g:12001
 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.
 Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoretical Computer Science 12 (1980), 97108. MR 82a:68078
 9.
 R. G. E. Pinch, The Carmichael numbers up to , Math. Comp. 61 (1993), 381389. MR 93m:11137
 10.
 , All Carmichael numbers with three prime factors up to , http://www.chalcedon.demon.co.uk/carpsp.html.
 11.
 J. M. Pollard, A MonteCarlo method for factorization, BIT 15 (1975), 331334. MR 52:13611
 12.
 C. Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The pseudoprimes to , Math. Comp. 35 (1980), 10031026. MR 82g:10030
 13.
 M. O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128138. MR 81f:10003
 14.
 Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), 863872. MR 2001g:11009
 15.
 , Using Lucas Sequences to Factor Large Integers Near Group Orders, The Fibonacci Quarterly 39 (2001), 228237. MR 2002c:11173
 16.
 , A oneparameter quadraticbase version of the BailliePSW probable prime test, Math. Comp. 71 (2002), 16991734. MR 2003f:11191
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
Min Tang
Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, Peoples Republic of China
DOI:
http://dx.doi.org/10.1090/S002557180301545X
PII:
S 00255718(03)01545X
Keywords:
Strong pseudoprimes,
Carmichael numbers,
RabinMiller test,
biquadratic residue characters,
cubic residue characters,
Chinese remainder theorem
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.
Article copyright:
© Copyright 2003
American Mathematical Society
