A pseudoprime is a

probable prime In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific con ...

(an

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

that shares a property common to all

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

s) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy. Some sources use the term pseudoprime to describe all probable primes, both

composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...

s and actual primes. Pseudoprimes are of primary importance in

public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

, which makes use of the difficulty of factoring large numbers into their prime factors.

Carl Pomerance Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number ...

estimated in 1988 that it would cost $10 million to factor a number with 144 digits, and $100 billion to factor a 200-digit number (the cost today is dramatically lower but still prohibitively high). But finding two large prime numbers as needed for this use is also expensive, so various probabilistic primality tests are used, some of which in rare cases inappropriately deliver composite numbers instead of primes. On the other hand, deterministic primality tests, such as the

AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Determi ...

, do not give

false positive A false positive is an error in binary classification in which a test result incorrectly indicates the presence of a condition (such as a disease when the disease is not present), while a false negative is the opposite error, where the test resul ...

s; there are no pseudoprimes with respect to them.

Fermat pseudoprimes

Fermat's little theorem states that if ''p'' is prime and ''a'' is

coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...

to ''p'', then ''a''^''p''−1 − 1 is

divisible In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...

by ''p''. For an integer ''a'' > 1, if a composite integer ''x'' divides ''a''^''x''−1 − 1, then ''x'' is called a Fermat pseudoprime to base ''a''. It follows that if ''x'' is a Fermat pseudoprime to base ''a'', then ''x'' is coprime to ''a''. Some sources use variations of this definition, for example to allow only odd numbers to be pseudoprimes. An integer ''x'' that is a Fermat pseudoprime to all values of ''a'' that are coprime to ''x'' is called a

Carmichael number In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation: :b^n\equiv b\pmod for all integers b. The relation may also be expressed in the form: :b^\equiv 1\pmod. for all integers ...

Classes

Catalan pseudoprime In mathematics, a Catalan pseudoprime is an odd composite number ''n'' satisfying the congruence : (-1)^ \cdot C_ \equiv 2 \pmod n, where ''Cm'' denotes the ''m''-th Catalan number. The congruence also holds for every odd prime number ''n'' that ...

Elliptic pseudoprime In number theory, a pseudoprime is called an elliptic pseudoprime for (''E'', ''P''), where ''E'' is an elliptic curve defined over the field of rational numbers with complex multiplication by an order in \mathbb \big(\sqrt \big), having equat ...

Euler pseudoprime In arithmetic, an odd composite integer ''n'' is called an Euler pseudoprime to base ''a'', if ''a'' and ''n'' are coprime, and : a^ \equiv \pm 1\pmod (where ''mod'' refers to the modulo operation). The motivation for this definition is the f ...

Euler–Jacobi pseudoprime In number theory, an odd integer ''n'' is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base ''a'', if ''a'' and ''n'' are coprime, and :a^ \equiv \left(\frac\right)\pmod where \left(\frac\right) is the J ...

Fermat pseudoprime In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Definition Fermat's little theorem states that if ''p'' is prime and ''a'' is coprime to ''p'', then ''a'p''− ...

Frobenius pseudoprime In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to pol ...

* Lucas pseudoprime *

Perrin pseudoprime In mathematics, the Perrin numbers are defined by the recurrence relation : for , with initial values :. The sequence of Perrin numbers starts with : 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ... The number of different maximal ...

* Somer–Lucas pseudoprime *

Strong pseudoprime A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes". Unlike the Fermat pseudoprimes, for which there ex ...

References

{{Classes of natural numbers