## 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).

 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 .'' Math. Comput. 35, 1003-1026, 1980. Available electronically from ftp://sable.ox.ac.uk/pub/math/primes/ps2.Z.

© 1996-9 Eric W. Weisstein
1999-05-26