Some new kinds of pseudoprimes

Author:
Jerzy Browkin

Journal:
Math. Comp. **73** (2004), 1031-1037

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

DOI:
https://doi.org/10.1090/S0025-5718-03-01617-X

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 -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]**J. Brillhart, D.H. Lehmer, J.L. Selfridge,*New primality criteria and factorizations of*, 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*, 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**

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:
https://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