pseudoprime


A pseudoprimeMathworldPlanetmathPlanetmath is a composite numberMathworldPlanetmath p that passes a given primality test. In other words, a pseudoprime is a false positive on a primality test.

The primality test is usually a power congruenceMathworldPlanetmath to a given base b that is coprimeMathworldPlanetmath to p, such as bp-11modp (from Fermat’s little theorem). For example, if p is an odd prime, then the congruence 2p-11modp will be true, but in reverse, p can satisfy the congruence but turn out to be an odd composite number. Such pseudoprimes are then called pseudoprime to base b, and in our example with b=2, the first few are 341, 561, 645, 1105, 1387, 1729, 1905 (A001567 in Sloane’s OEIS). According to Neil Sloane, writing in the OEIS, the term “pseudoprime” is sometimes used specifically to refer to pseudoprimes to base 2. These are sometimes called Sarrus numbers.

Another kind of pseudoprimes are those in which a composite p divides an element it indexes in a Fibonacci-like sequence. For example, a Perrin pseudoprimeMathworldPlanetmath p divides ap, where an is the n-th element in the Perrin sequenceMathworldPlanetmath.

References

  • 1 R. Crandall & C. Pomerance, Prime NumbersMathworldPlanetmath: A Computational Perspective, Springer, NY, 2001: 5.1
Title pseudoprime
Canonical name Pseudoprime
Date of creation 2013-03-22 16:49:44
Last modified on 2013-03-22 16:49:44
Owner CompositeFan (12809)
Last modified by CompositeFan (12809)
Numerical id 6
Author CompositeFan (12809)
Entry type Definition
Classification msc 11A51