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.
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.
However, no numbers are actually known that pass advanced probabilistic tests (such
as Rabin-Miller) yet are actually composite.
The state of the art in deterministic primality testing for arbitrary numbers is elliptic curve primality proving.
As of Feb. 2009, the largest number certified by the program PRIMO
(7993 decimal digits) took eight months on a 2-GHz processor.
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.
(Bernstein 2002, Clark 2002, Indian Institute of
Technology 2002, Pomerance 2002ab, Robinson 2002). Their algorithm has come to be
called the AKS primality test.
