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 Free Access

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 -pseudoprimes and elementary Abelian -pseudoprimes. It turns out that every which is a strong pseudoprime to bases 2, 3 and 5, is not a Sylow -pseudoprime to two of these bases for an appropriate prime

We also give examples of strong pseudoprimes to many bases which are not Sylow -pseudoprimes to two bases only, where or

**[AKS]**M. Agrawal, N. Kayal, N. Saxena,*PRIMES is in P*,`http://www.cse.iitk.ac.in`.**[BLS]**John Brillhart, D. H. Lehmer, and J. L. Selfridge,*New primality criteria and factorizations of 2^{𝑚}±1*, Math. Comp.**29**(1975), 620–647. MR**0384673**, 10.1090/S0025-5718-1975-0384673-1**[J]**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**[KP]**Sergei Konyagin and Carl Pomerance,*On primes recognizable in deterministic polynomial time*, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 176–198. MR**1425185**, 10.1007/978-3-642-60408-9_15**[PSW]**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**[ZZ]**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

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:
http://dx.doi.org/10.1090/S0025-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

Published electronically:
August 20, 2003

Article copyright:
© Copyright 2003
American Mathematical Society