Primality Test

A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization).

Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving. Probabilistic tests can potentially (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically.

For an odd integer , classical primality tests can use known prime factors of or , together with suitable modular conditions, to prove that is prime. A complete prime factorization of or is not always necessary. Examples include Pocklington's theorem and the methods of Brillhart et al. (1975), which can also combine information from both and .

A number that passes a probabilistic test but is in fact composite is known as a pseudoprime. There are many specific types of pseudoprimes, the most common being the Fermat pseudoprimes, which are composites that nonetheless satisfy Fermat's little theorem.

The Rabin-Miller strong pseudoprime test is a particularly efficient test. The Wolfram Language implements the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]. Like many such algorithms, it is a probabilistic test using pseudoprimes. In order to guarantee primality, a much slower deterministic algorithm must be used. As of Oct. 2026, no composite number is known to pass the Baillie-PSW primality test.

The state of the art in deterministic primality testing for arbitrary numbers is elliptic curve primality proving. As of Oct. 2026, the largest number certified by the program PRIMO is the repunit prime , with 49,081 decimal digits. Its certification by P. Underwood in 2022 took 20 months on a 64-core AMD Ryzen Threadripper 3990X (Martin).

Unlike prime factorization, primality testing was long believed to be a P-problem (Wagon 1991). This had not been demonstrated, however, until Agrawal et al. (2002) unexpectedly discovered a polynomial time algorithm for primality testing that has asymptotic complexity of (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002). Their algorithm has come to be called the AKS primality test.