Notes on some new kinds of pseudoprimes

Author:
Zhenxiang Zhang

Journal:
Math. Comp. **75** (2006), 451-460

MSC (2000):
Primary 11A15; Secondary 11A51, 11Y11

Published electronically:
September 15, 2005

MathSciNet review:
2176408

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: J. Browkin defined in his recent paper (Math. Comp. **73** (2004), pp. 1031-1037) 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 Syl-upsp for short, if it is a Syl-psp for all the first small prime factors of , where is the number of distinct prime factors of . We find and tabulate all the 17 Syl-upsp's and some Syl-upsp '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**, 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**, 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 Springer-Verlag, New York, 2000. With 1 CD-ROM (Windows, Macintosh and UNIX). MR**1756372****5.**Jerzy Browkin,*Some new kinds of pseudoprimes*, Math. Comp.**73**(2004), no. 246, 1031–1037 (electronic). MR**2031424**, 10.1090/S0025-5718-03-01617-X**6.**Richard Crandall and Carl Pomerance,*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158****7.**Gerhard Jaeschke,*On strong pseudoprimes to several bases*, Math. Comp.**61**(1993), no. 204, 915–926. MR**1192971**, 10.1090/S0025-5718-1993-1192971-8**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 ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295****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**, 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**, 10.1090/S0025-5718-1980-0572872-7**12.**Michael O. Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, 10.1016/0022-314X(80)90084-0**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**, 10.1090/S0025-5718-00-01215-1**15.**Zhenxiang Zhang,*A one-parameter quadratic-base version of the Baillie-PSW probable prime test*, Math. Comp.**71**(2002), no. 240, 1699–1734 (electronic). MR**1933051**, 10.1090/S0025-5718-02-01424-2**16.**Zhenxiang Zhang,*Finding 𝐶₃-strong pseudoprimes*, Math. Comp.**74**(2005), no. 250, 1009–1024 (electronic). MR**2114662**, 10.1090/S0025-5718-04-01693-X**17.**Zhenxiang Zhang and Min Tang,*Finding strong pseudoprimes to several bases. II*, Math. Comp.**72**(2003), no. 244, 2085–2097 (electronic). MR**1986825**, 10.1090/S0025-5718-03-01545-X**18.**Günter M. Ziegler,*The great prime number record races*, Notices Amer. Math. Soc.**51**(2004), no. 4, 414–416. MR**2039814**

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:
https://doi.org/10.1090/S0025-5718-05-01775-8

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.