The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a
deterministic primality-proving algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
created and published by
Manindra Agrawal,
Neeraj Kayal, and
Nitin Saxena, computer scientists at the
Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P".
The algorithm was the first one which is able to determine in
polynomial time, whether a given number is
prime
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 ...
or
composite without relying on
mathematical conjectures such as the
generalized Riemann hypothesis. The proof is also notable for not relying on the field of
analysis
Analysis (: analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (38 ...
. In 2006 the authors received both the
Gödel Prize and
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...
for their work.
Importance
AKS is the first primality-proving algorithm to be simultaneously ''general'', ''polynomial-time'', ''deterministic'', and ''unconditionally correct''. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four.
* The AKS algorithm can be used to verify the primality of any general number given. Many fast primality tests are known that work only for numbers with certain properties. For example, the
Lucas–Lehmer test works only for
Mersenne number
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17t ...
s, while
Pépin's test can be applied to
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat (1601–1665), the first known to have studied them, is a natural number, positive integer of the form:F_ = 2^ + 1, where ''n'' is a non-negative integer. The first few Fermat numbers ...
s only.
* The maximum running time of the algorithm can be bounded by a
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
over the number of digits in the target number.
ECPP and
APR conclusively prove or disprove that a given number is prime, but are not known to have polynomial time bounds for all inputs.
* The algorithm is guaranteed to distinguish
deterministically whether the target number is prime or composite. Randomized tests, such as
Miller–Rabin and
Baillie–PSW, can test any given number for primality in polynomial time, but are known to produce only a probabilistic result.
* The correctness of AKS is not conditional on any subsidiary unproven
hypothesis
A hypothesis (: hypotheses) is a proposed explanation for a phenomenon. A scientific hypothesis must be based on observations and make a testable and reproducible prediction about reality, in a process beginning with an educated guess o ...
. In contrast, Miller's version of the
Miller–Rabin test is fully deterministic and runs in polynomial time over all inputs, but its correctness depends on the truth of the yet-unproven
generalized Riemann hypothesis.
While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a
galactic algorithm. For 64-bit inputs, the
Baillie–PSW test is deterministic and runs many orders of magnitude faster. For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is ''far'' superior to AKS. Additionally, ECPP can output a
primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.
Concepts
The AKS primality test is based upon the following theorem: Given an integer
and integer
coprime
In number theory, 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 equiv ...
to
,
is prime if and only if the
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group (mathematics), group, ring (mathematics), ring, or vector space) that is compatible with the structure in the ...
holds within the polynomial ring