Notes on some new kinds of pseudoprimes
Author:
Zhenxiang Zhang
Journal:
Math. Comp. 75 (2006), 451460
MSC (2000):
Primary 11A15; Secondary 11A51, 11Y11
Published electronically:
September 15, 2005
MathSciNet review:
2176408
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: J. Browkin defined in his recent paper (Math. Comp. 73 (2004), pp. 10311037) some new kinds of pseudoprimes, called Sylow pseudoprimes and elementary Abelian pseudoprimes. He gave examples of strong pseudoprimes to many bases which are not Sylow pseudoprime to two bases only, where or . In this paper, in contrast to Browkin's examples, we give facts and examples which are unfavorable for Browkin's observation to detect compositeness of odd composite numbers. In Section 2, we tabulate and compare counts of numbers in several sets of pseudoprimes and find that most strong pseudoprimes are also Sylow pseudoprimes to the same bases. In Section 3, we give examples of Sylow pseudoprimes to the first several prime bases for the first several primes . We especially give an example of a strong pseudoprime to the first six prime bases, which is a Sylow pseudoprime to the same bases for all . In Section 4, we define to be a fold Carmichael Sylow pseudoprime, if it is a Sylow pseudoprime to all bases prime to for all the first smallest odd prime factors of . We find and tabulate all three fold Carmichael Sylow pseudoprimes . In Section 5, we define a positive odd composite to be a Sylow uniform pseudoprime to bases , or a Sylupsp for short, if it is a Sylpsp for all the first small prime factors of , where is the number of distinct prime factors of . We find and tabulate all the 17 Sylupsp's and some Sylupsp 's . Comparisons of effectiveness of Browkin's observation with Miller tests to detect compositeness of odd composite numbers are given in Section 6.
 1.
Manindra
Agrawal, Neeraj
Kayal, and Nitin
Saxena, PRIMES is in P, Ann. of Math. (2) 160
(2004), no. 2, 781–793. MR 2123939
(2006a:11170), http://dx.doi.org/10.4007/annals.2004.160.781
 2.
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
 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.
David
Bressoud and Stan
Wagon, A course in computational number theory, Key College
Publishing, Emeryville, CA; in cooperation with SpringerVerlag, New York,
2000. With 1 CDROM (Windows, Macintosh and UNIX). MR 1756372
(2001f:11200)
 5.
Jerzy
Browkin, Some new kinds of
pseudoprimes, Math. Comp.
73 (2004), no. 246, 1031–1037 (electronic). MR 2031424
(2004m:11006), http://dx.doi.org/10.1090/S002557180301617X
 6.
Richard
Crandall and Carl
Pomerance, Prime numbers, SpringerVerlag, New York, 2001. A
computational perspective. MR 1821158
(2002a:11007)
 7.
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
 8.
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)
 9.
R. G. E. Pinch, The Carmichael numbers up to , preprint, 1998. http://www.chalcedon. demon.co.uk/carpsp.html.
 10.
Richard
G. E. Pinch, The pseudoprimes up to 10¹³,
Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci.,
vol. 1838, Springer, Berlin, 2000, pp. 459–473. MR 1850626
(2002g:11177), http://dx.doi.org/10.1007/10722028_30
 11.
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
 12.
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
 13.
Anton Stiglic, The PRIMES is in P little FAQ, http://crypto.cs.mcgill.ca/~stiglic/ PRIMES_P_FAQ.html
 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, 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
 16.
Zhenxiang
Zhang, Finding 𝐶₃strong
pseudoprimes, Math. Comp.
74 (2005), no. 250, 1009–1024 (electronic). MR 2114662
(2005k:11243), http://dx.doi.org/10.1090/S002557180401693X
 17.
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
 18.
Günter
M. Ziegler, The great prime number record races, Notices Amer.
Math. Soc. 51 (2004), no. 4, 414–416. MR 2039814
(2005a:11198)
 1.
 M. Agrawal, N. Kayal and N. Saxena, Primes is in P, Annals of Mathematics, 160 (2004), 781793; preprint, August 2002, http://www.cse.iitk.ac.in. MR 2123939
 2.
 W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Annals of Math. 140 (1994), 703722. MR 1283874 (95k:11114)
 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.
 D. M. Bressoud and S. Wagon, A course in computational number theory, Key College Publishing, SpringerVerlag, New York, 2000. MR 1756372 (2001f:11200)
 5.
 Jerzy Browkin, Some new kinds of pseudoprimes, Math. Comp. 246 (2004), 10311037. MR 2031424 (2004m:11006)
 6.
 R. Crandall and C. Pomerance, Numbers, a computational perspective, SpringerVerlag, New York, 2001. MR 1821158 (2002a:11007)
 7.
 G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), 915926. MR 1192971 (94d:11004)
 8.
 G. Miller, Riemann's hypothesis and tests for primality, J. Comput. and System Sci. 13 (1976), 300317. MR 0480295 (58:470a)
 9.
 R. G. E. Pinch, The Carmichael numbers up to , preprint, 1998. http://www.chalcedon. demon.co.uk/carpsp.html.
 10.
 , The pseudoprimes up to , Algorithmic number theory (Leiden, 2000), 459473, Lecture Notes in Comput. Sci., 1838, Springer, Berlin, 2000. MR 1850626 (2002g:11177) ftp://ftp.dpmms.cam.ac.uk/pub/PSP
 11.
 C. Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The pseudoprimes to , Math. Comp. 35 (1980), 10031026. MR 0572872 (82g:10030)
 12.
 M. O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128138. MR 0566880 (81f:10003)
 13.
 Anton Stiglic, The PRIMES is in P little FAQ, http://crypto.cs.mcgill.ca/~stiglic/ PRIMES_P_FAQ.html
 14.
 Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), 863872. MR 1697654 (2001g:11009) http://www.ams.org/journalgetitem?pii=S0025571800012151
 15.
 , A oneparameter quadraticbase version of the BailliePSW probable prime test, Math. Comp. 71 (2002), 16991734. MR 1933051 (2003f:11191) http://www.ams.org/journalgetitem?pii=S0025571802014242
 16.
 , Finding strong pseudoprimes, Math. Comp. 74 (2005), 10091024. MR 2114662
 17.
 Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Math. Comp. 72 (2003), 20852097. MR 1986825 (2004c:11008) http://www.ams.org/journalgetitem?pii=S002557180301545X
 18.
 Günter M. Ziegler, The great prime number record races, Notices of the AMS 51:4 (2004), 414416. MR 2039814 (2005a:11198)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11A15,
11A51,
11Y11
Retrieve articles in all journals
with MSC (2000):
11A15,
11A51,
11Y11
Additional Information
Zhenxiang Zhang
Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, People’s Republic of China
Email:
zhangzhx@mail.ahwhptt.net.cn, ahnu_zzx@sina.com
DOI:
http://dx.doi.org/10.1090/S0025571805017758
PII:
S 00255718(05)017758
Keywords:
Strong pseudoprimes,
Miller tests,
Sylow $p$pseudoprimes,
elementary Abelian $p$pseudoprimes,
$k$fold Carmichael Sylow pseudoprimes,
Sylow uniform pseudoprimes
Received by editor(s):
September 18, 2004
Published electronically:
September 15, 2005
Additional Notes:
This work was supported by the NSF of China Grant 10071001, and the SF of the Education Department of Anhui Province Grant 2002KJ131
Article copyright:
© Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
