Fermat pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Definition[edit]
Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For a positive integer a, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a.
[1]: Def. 3.32
In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a.[2] The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the Chinese hypothesis.
The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes the
Fermat primality test for the base 2.
Pseudoprimes to base 2 are sometimes called Sarrus numbers, after P. F. Sarrus who discovered that 341 has this property, Poulet numbers, after P. Poulet who made a table of such numbers, or Fermatians (sequence A001567 in the OEIS).
A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood.
An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.[2][1]: Def. 3.34
Properties[edit]
Distribution[edit]
There are infinitely many pseudoprimes to any given base a > 1. In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base a > 1: let A = (ap - 1)/(a - 1) and let B = (ap + 1)/(a + 1), where p is a prime number that does not divide a(a2 - 1). Then n = AB is composite, and is a pseudoprime to base a.[3][4] For example, if a = 2 and p = 5, then A = 31, B = 11, and n = 341 is a pseudoprime to base 2.
In fact, there are infinitely many strong pseudoprimes to any base greater than 1 (see Theorem 1 of
[5]) and infinitely many Carmichael numbers,[6] but they are comparatively rare. There are three pseudoprimes to base 2 below 1000, 245 below one million, and 21853 less than 25·109. There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (see Table 1 of [5]).
Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all Fermat composites and Mersenne composites.
The probability of a composite number n passing the Fermat test approaches zero for . Specifically, Kim and Pomerance showed the following: The probability that a random odd number n ≤ x is a Fermat pseudoprime to a random base is less than 2.77·10-8 for x= 10100, and is at most (log x)-197<10-10,000 for x≥10100,000.[7]
Applications[edit]
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 an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test.