Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

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 $p$-pseudoprimes and elementary Abelian $p$-pseudoprimes. He gave examples of strong pseudoprimes to many bases which are not Sylow $p$-pseudoprime to two bases only, where $p=2$ or $3$.

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 $2$-pseudoprimes to the same bases. In Section 3, we give examples of Sylow $p$-pseudoprimes to the first several prime bases for the first several primes $p$. We especially give an example of a strong pseudoprime to the first six prime bases, which is a Sylow $p$-pseudoprime to the same bases for all $p\in\{2,3,5,7,11,13\}$. In Section 4, we define $n$ to be a $k$-fold Carmichael Sylow pseudoprime, if it is a Sylow $p$-pseudoprime to all bases prime to $n$ for all the first $k$ smallest odd prime factors $p$ of $n-1$. We find and tabulate all three $3$-fold Carmichael Sylow pseudoprimes $<10^{16}$. In Section 5, we define a positive odd composite $n$ to be a Sylow uniform pseudoprime to bases $b_1,\ldots,b_k$, or a Syl-upsp $(b_1,\ldots,b_k)$ for short, if it is a Syl$_p$-psp $(b_1,\ldots,b_k)$for all the first $\omega(n-1)-1$ small prime factors $p$ of $n-1$, where $\omega(n-1)$ is the number of distinct prime factors of $n-1$. We find and tabulate all the 17 Syl-upsp$(2,3,5)$'s $<10^{16}$ and some Syl-upsp $(2,3,5,7,11)$'s $<10^{24}$. Comparisons of effectiveness of Browkin's observation with Miller tests to detect compositeness of odd composite numbers are given in Section 6.

References [Enhancements On Off] (What's this?)

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

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.