Pseudoprime

A pseudoprime is a Composite number which passes a test or sequence of tests which fail for most Composite numbers. Unfortunately, some authors drop the ``Composite'' requirement, calling any number which passes the specified tests a pseudoprime even if it is Prime. Pomerance, Selfridge, and Wagstaff (1980) restrict their use of ``pseudoprime'' to Odd Composite numbers. ``Pseudoprime'' used without qualification means Fermat Pseudoprime.

Carmichael Numbers are Odd Composite numbers which are pseudoprimes to every base; they are sometimes called Absolute Pseudoprimes. The following table gives the number of Fermat Pseudoprimes psp, Euler Pseudoprimes epsp, and Strong Pseudoprimes spsp to the base 2, as well as Carmichael Numbers CN which are less the first few powers of 10 (Guy 1994).

	$10^3$	$10^4$	$10^5$	$10^6$	$10^7$	$10^8$	$10^9$	$10^{10}$
psp(2)	3	22	78	245	750	2057	5597	14884
epsp(2)	1	12	36	114	375	1071	2939	7706
spsp(2)	0	5	16	46	162	488	1282	3291
CN	1	7	16	43	105	255	646	1547

See also Carmichael Number, Elliptic Pseudoprime, Euler Pseudoprime, Euler-Jacobi Pseudoprime, Extra Strong Lucas Pseudoprime, Fermat Pseudoprime, Fibonacci Pseudoprime, Frobenius Pseudoprime, Lucas Pseudoprime, Perrin Pseudoprime, Probable Prime, Somer-Lucas Pseudoprime, Strong Elliptic Pseudoprime, Strong Frobenius Pseudoprime, Strong Lucas Pseudoprime, Strong Pseudoprime

References

Grantham, J. ``Frobenius Pseudoprimes.'' http://www.clark.net/pub/grantham/pseudo/pseudo1.ps

Grantham, J. ``Pseudoprimes/Probable Primes.'' http://www.clark.net/pub/grantham/pseudo.

Guy, R. K. ``Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.'' §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. ``The Pseudoprimes to $25\cdot 10^9$.'' Math. Comput. 35, 1003-1026, 1980. Available electronically from ftp://sable.ox.ac.uk/pub/math/primes/ps2.Z.