Pseudoprime

A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. Pseudoprimes can be classified according to which property they satisfy.

Related Topics:
Probable prime - Integer - Prime number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The most important class of pseudoprimes come from Fermat's little theorem and hence are called Fermat pseudoprimes. This theorem states that if p is prime and a is coprime to p, then ap-1 - 1 is divisible by p. If a number x is not prime, a is coprime to x and x divides ax-1 - 1, then x is called a pseudoprime to base a. A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number.

Related Topics:
Fermat's little theorem - Coprime - Divisible - Carmichael number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The smallest Fermat pseudoprime for the base 2 is 341. It is not a prime, since it equals 11 · 31, nevertheless it satisfies Fermat's little theorem; 2341=2 (mod 341).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The rarity of such pseudoprimes has important practical implications. For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user is willing to tolerate a very small chance that the number found is not a prime number but a pseudoprime, then much faster and simpler tests are possible. Probabilistic algorithms such as the Fermat primality test, the Solovay-Strassen primality test, and the Miller-Rabin primality test are refinements of this idea.

Related Topics:
Public-key cryptography - RSA - Deterministic - Probabilistic algorithm - Fermat primality test - Solovay-Strassen primality test - Miller-Rabin primality test

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

There are infinitely many pseudoprimes (in fact infinitely many Carmichael numbers), but they are rather rare. There are only 3 pseudo-primes to base 2 below 1000, and below a million there are only 245. Pseudoprimes to base 2 are called Poulet numbers or sometimes Sarrus numbers or Fermatians {{OEIS|id=A001567}}. The Poulet numbers and Carmichael numbers (in bold) up to 41041 are:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A Poulet number all of whose divisors d divide 2d - 2 is called

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

super-Poulet number. There are an infinitely many Poulet numbers which are not super-Poulet Numbers.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The first smallest pseudoprimes for bases a ≤ 200 are given in the following table; the colors mark the number of prime factors.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~