Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Some new kinds of pseudoprimes

Author: Jerzy Browkin
Journal: Math. Comp. 73 (2004), 1031-1037
MSC (2000): Primary 11A15; Secondary 11A51, 11Y11
Published electronically: August 20, 2003
Erratum: Math. Comp. 74 (2005), 1573.
MathSciNet review: 2031424
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We define some new kinds of pseudoprimes to several bases, which generalize strong pseudoprimes. We call them Sylow $p$-pseudoprimes and elementary Abelian $p$-pseudoprimes. It turns out that every $n<10^{12},$ which is a strong pseudoprime to bases 2, 3 and 5, is not a Sylow $p$-pseudoprime to two of these bases for an appropriate prime $p\vert n-1.$

We also give examples of strong pseudoprimes to many bases which are not Sylow $p$-pseudoprimes to two bases only, where $p=2$ or $3.$

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

  • [AKS] M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P,
  • [BLS] J. Brillhart, D.H. Lehmer, J.L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620-647. MR 52:5546
  • [J] G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), 915-926. MR 94d:11004
  • [KP] S. Konyagin, C. Pomerance, On primes recognizable in deterministic polynomial time, The mathematics of Paul Erdos (R.L. Graham, J. Nesetril, eds.), vol. I, Springer, Berlin, 1997, pp. 176-198.MR 98a:11184
  • [PSW] C. Pomerance, J.L. Selfridge, S.S. Wagstaff, Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), 1003-1026.MR 82g:10030
  • [ZZ] Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), 863-872. MR 2001g:11009

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

Jerzy Browkin
Affiliation: Institute of Mathematics, University of Warsaw, ul. Banacha 2, PL–02–097 Warsaw, Poland

Keywords: Strong pseudoprimes, primality testing
Received by editor(s): February 19, 1998
Received by editor(s) in revised form: October 23, 2002
Published electronically: August 20, 2003
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society