Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Some new kinds of pseudoprimes

Author(s): Jerzy Browkin.
Journal: Math. Comp. 73 (2004), 1031-1037.
MSC (2000): Primary 11A15; Secondary 11A51, 11Y11
Posted: August 20, 2003
Errata: Math. Comp. 74 (2005), 1573.
Retrieve article in: 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:

[AKS]
M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, http://www.cse.iitk.ac.in.

[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
Email: bro@mimuw.edu.pl

DOI: 10.1090/S0025-5718-03-01617-X
PII: S 0025-5718(03)01617-X
Keywords: Strong pseudoprimes, primality testing
Received by editor(s): February 19, 1998
Received by editor(s) in revised form: October 23, 2002
Posted: August 20, 2003
Copyright of article: Copyright 2003, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google