Some new kinds of pseudoprimes

Browkin, Jerzy

doi:10.1090/S0025-5718-03-01617-X

Some new kinds of pseudoprimes
HTML articles powered by AMS MathViewer

by Jerzy Browkin PDF

Math. Comp. 73 (2004), 1031-1037 Request permission

Erratum: Math. Comp. 74 (2005), 1573-1573.

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

M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, http://www.cse.iitk.ac.in.
John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1
Gerhard Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), no. 204, 915–926. MR 1192971, DOI 10.1090/S0025-5718-1993-1192971-8
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, DOI 10.1007/978-3-642-60408-9_{1}5
Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
Zhenxiang Zhang, Finding strong pseudoprimes to several bases, Math. Comp. 70 (2001), no. 234, 863–872. MR 1697654, DOI 10.1090/S0025-5718-00-01215-1