TOPICS
Search

Pseudoprime


A pseudoprime is a composite number that passes a test or sequence of tests that fail for most composite numbers. Unfortunately, some authors drop the "composite" requirement, calling any number that 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, i.e., a composite number that nonetheless satisfies Fermat's little theorem to some base or set of bases.

Carmichael numbers are odd composite numbers that are Fermat pseudoprimes to every base; they are sometimes called absolute pseudoprimes.

The following table gives the number of Poulet numbers psp(2), Euler-Jacobi pseudoprimes ejpsp(2), and strong pseudoprimes spsp(2) to the base 2, and Carmichael numbers CN that are smaller than the first few powers of 10 (Guy 1994). The table below extend Guy's table with the results of Pinch, who calculated the number of pseudoprimes up to 10^(13).

10^npsp(2)ejpsp(2)spsp(2)CN
SloaneA055550A055551A055552A055553
Sloane countsA001567A047713A001262A002997
10^10000
10^20000
10^33101
10^4221257
10^578361616
10^62451144643
10^7750375162105
10^820571071488255
10^9559729391282646
10^(10)14884770632911547
10^(11)389752041786073605
10^(12)10162953332224078241
10^(13)2642391248825889219279

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, Poulet Number, Probable Prime, Somer-Lucas Pseudoprime, Strong Elliptic Pseudoprime, Strong Frobenius Pseudoprime, Strong Lucas Pseudoprime, Strong Pseudoprime

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Caldwell, C. K. "Prime Links++." http://primes.utm.edu/links/theory/finding_and_proving/probable_primality/.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.Pinch, R. G. E. "The Pseudoprimes Up to 10^(13)." ftp://ftp.dpmms.cam.ac.uk/pub/PSP/.Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25·10^9." Math. Comput. 35, 1003-1026, 1980. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.Sloane, N. J. A. Sequences A001262, A001567/M5441, A002997/M5462, A047713, A055550, A055551, A055552, and A055553 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Pseudoprime

Cite this as:

Weisstein, Eric W. "Pseudoprime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Pseudoprime.html

Subject classifications