AKS primality test
Encyclopedia
The AKS primality test is a deterministic
primality-proving
algorithm
created and published by three Indian Institute of Technology Kanpur
computer scientists, Manindra Agrawal
, Neeraj Kayal
, and Nitin Saxena
, on August 6, 2002, in a paper titled "PRIMES is in P". The authors received many accolades, including the 2006 Gödel Prize
and the 2006 Fulkerson Prize
, for this work.
The algorithm determines whether a number is prime
or composite
within polynomial time.
holds for all integers a coprime
to n (or even just for some such integer a, in particular for a = 1). Note that x is an open variable. It is never substituted by a number; instead you have to expand
and compare the coefficients of the x powers.
This theorem is a generalization to polynomials of Fermat's little theorem
, and can easily be proven using the binomial theorem
together with the following property of the binomial coefficient
:
for all 
if and only if n is prime.
While the relation (1) constitutes a primality test in itself, verifying it takes exponential time. Therefore, to reduce the computational complexity
, AKS makes use of the related congruence
which is the same as:
for some polynomials f and g. This congruence can be checked in polynomial time. Note that all primes satisfy this relation (choosing g = 0 in (3) gives (1), which holds for n prime). However, some composite numbers also satisfy the relation. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that, if the congruence holds for all such a in A, then n must be prime.
. In other words, the algorithm takes less time than the twelfth power of the number of digits in n times a polylogarithmic (in the number of digits) factor. However, the upper bound proved in the paper was rather loose; indeed, a widely held conjecture about the distribution of the Sophie Germain prime
s would, if true, immediately cut the worst case down to Õ
.
In the months following the discovery, new variants appeared (Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra and Pomerance 2003), which improved the speed of computation by orders of magnitude. Due to the existence of the many variants, Crandall and Papadopoulos refer to the "AKS-class" of algorithms in their scientific paper "On the implementation of AKS-class primality tests", published in March 2003.
In response to some of these variants, and to other feedback, the paper "PRIMES is in P" was updated with a new formulation of the AKS algorithm and of its proof of correctness. (This version was eventually published in Annals of Mathematics
.) While the basic idea remained the same, r was chosen in a new manner, and the proof of correctness was more coherently organized. While the previous proof had relied on many different methods, the new version relied almost exclusively on the behavior of cyclotomic polynomials over finite fields. The new version also allowed for an improved bound on the time complexity, which can now be shown by simple methods to be Õ
. Using additional results from sieve theory
, this can be further reduced to Õ
.
In 2005, Carl Pomerance
and H. W. Lenstra, Jr.
demonstrated a variant of AKS that runs in Õ(log6(n)) operations, where n is the number to be tested – a marked improvement over the initial Õ(log12(n)) bound in the original algorithm. An updated version of the paper is also available.
Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ
if a certain conjecture made by Bhattacharjee and Pandey in 2001 is true; however this conjecture has been shown to be heuristically false.
Here or(n) is the multiplicative order
of n modulo
r, log is the binary logarithm
, and
is Euler's totient function
of r.
If n is a prime number, the algorithm will always return prime: since n is prime, steps 1 and 3 will never return composite. Step 5 will also never return composite, because (2) is true for all prime numbers n. Therefore, the algorithm will return prime either in step 4 or in step 6.
Conversely, if n is composite, the algorithm will always return composite: if the algorithm returns prime, then this will occur in either step 4 or step 6. In the first case, since n ≤ r, n has a factor a ≤ r such that 1 < gcd(a,n) < n, which will return composite. The remaining possibility is that the algorithm returns prime in step 6. The authors' article proves that this will not happen because the multiple equalities tested in step 5 are sufficient to guarantee that the output is composite.
Deterministic algorithm
In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
primality-proving
Primality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
created and published by three Indian Institute of Technology Kanpur
Indian Institute of Technology Kanpur
The Indian Institute of Technology Kanpur is a Central deemed University located in Uttar Pradesh, about 15 km north-west of the city of Kanpur in the Kalyanpur suburb....
computer scientists, Manindra Agrawal
Manindra Agrawal
Manindra Agrawal is a professor at the department of computer science and engineering and the Dean of Resource, Planning and Generation at the Indian Institute of Technology, Kanpur. He is also the recipient of the first Infosys Prize for Mathematics.-Early life:Manindra Agrawal obtained a...
, Neeraj Kayal
Neeraj Kayal
Neeraj Kayal is an Indian computer scientist. Kayal was born and raised in Guwahati, India.Kayal graduated with a B.Tech from the Computer Science Department of the Indian Institute of Technology, Kanpur , India in 2002...
, and Nitin Saxena
Nitin Saxena
Nitin Saxena is an Indian scientist, active in the fields of mathematics and theoretical computer science. His research focuses on topics in computational complexity, especially algebraic approaches....
, on August 6, 2002, in a paper titled "PRIMES is in P". The authors received many accolades, including the 2006 Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
and the 2006 Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
, for this work.
The algorithm determines whether a number is prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
or composite
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
within polynomial time.
Importance
The key significance of AKS is that it was the first published primality-proving algorithm to be simultaneously general, polynomial, deterministic, and unconditional. Previous algorithms had 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 for Mersenne numbers works only for Mersenne numbers, while Pépin's testPépin's testIn mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named for a French mathematician, Théophile Pépin.-Description of the test:...
can be applied to Fermat numbers only. - The maximum running time of the algorithm can be expressed as a polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
over the number of digits in the target number. ECPPElliptic curve primality provingElliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number . It is a general-purpose algorithm, meaning it does not depend on the number being of a special form...
and APRAdleman–Pomerance–Rumely primality testIn computational number theory, the Adleman–Pomerance–Rumely primality test is an algorithm for determining whether a number is prime. Unlike other, more efficient algorithms for this purpose, it avoids the use of random numbers, so it is a deterministic primality test. It is named after its...
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 deterministicallyDeterministic algorithmIn computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states...
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 hypothesisHypothesisA hypothesis is a proposed explanation for a phenomenon. The term derives from the Greek, ὑποτιθέναι – hypotithenai meaning "to put under" or "to suppose". For a hypothesis to be put forward as a scientific hypothesis, the scientific method requires that one can test it...
. In contrast, the Miller 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 hypothesisGeneralized Riemann hypothesisThe Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global L-functions, which are formally similar to the Riemann zeta-function...
.
Concepts
The AKS primality test is based upon the following theorem: An integer n (≥ 2) is prime if and only if the polynomial congruence relationholds for all integers a coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to n (or even just for some such integer a, in particular for a = 1). Note that x is an open variable. It is never substituted by a number; instead you have to expand
and compare the coefficients of the x powers.This theorem is a generalization to polynomials of Fermat's little theorem
Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
, and can easily be proven using the binomial theorem
Binomial theorem
In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the power n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with , and the coefficient a of...
together with the following property of the binomial coefficient
Binomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
:
for all if and only if n is prime.While the relation (1) constitutes a primality test in itself, verifying it takes exponential time. Therefore, to reduce the computational complexity
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, AKS makes use of the related congruence
which is the same as:
for some polynomials f and g. This congruence can be checked in polynomial time. Note that all primes satisfy this relation (choosing g = 0 in (3) gives (1), which holds for n prime). However, some composite numbers also satisfy the relation. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that, if the congruence holds for all such a in A, then n must be prime.
History and running time
In the first version of the above-cited paper, the authors proved the asymptotic time complexity of the algorithm to be Õ. In other words, the algorithm takes less time than the twelfth power of the number of digits in n times a polylogarithmic (in the number of digits) factor. However, the upper bound proved in the paper was rather loose; indeed, a widely held conjecture about the distribution of the Sophie Germain primeSophie Germain prime
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number...
s would, if true, immediately cut the worst case down to Õ
.In the months following the discovery, new variants appeared (Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra and Pomerance 2003), which improved the speed of computation by orders of magnitude. Due to the existence of the many variants, Crandall and Papadopoulos refer to the "AKS-class" of algorithms in their scientific paper "On the implementation of AKS-class primality tests", published in March 2003.
In response to some of these variants, and to other feedback, the paper "PRIMES is in P" was updated with a new formulation of the AKS algorithm and of its proof of correctness. (This version was eventually published in Annals of Mathematics
Annals of Mathematics
The Annals of Mathematics is a bimonthly mathematical journal published by Princeton University and the Institute for Advanced Study. It ranks amongst the most prestigious mathematics journals in the world by criteria such as impact factor.-History:The journal began as The Analyst in 1874 and was...
.) While the basic idea remained the same, r was chosen in a new manner, and the proof of correctness was more coherently organized. While the previous proof had relied on many different methods, the new version relied almost exclusively on the behavior of cyclotomic polynomials over finite fields. The new version also allowed for an improved bound on the time complexity, which can now be shown by simple methods to be Õ
. Using additional results from sieve theorySieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
, this can be further reduced to Õ
.In 2005, Carl Pomerance
Carl Pomerance
Carl Bernard Pomerance is a well-known 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 has at least 7 distinct prime factors. He immediately joined the faculty at the...
and H. W. Lenstra, Jr.
Hendrik Lenstra
Hendrik Willem Lenstra, Jr. is a Dutch mathematician.-Biography:Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978...
demonstrated a variant of AKS that runs in Õ(log6(n)) operations, where n is the number to be tested – a marked improvement over the initial Õ(log12(n)) bound in the original algorithm. An updated version of the paper is also available.
Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ
if a certain conjecture made by Bhattacharjee and Pandey in 2001 is true; however this conjecture has been shown to be heuristically false.Algorithm
The algorithm is as follows:- Input: integer n > 1.
- If n = ab for integers a > 0 and b > 1, output composite.
- Find the smallest r such that or(n) > log2(n).
- If 1 < gcdGreatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
(a,n) < n for some a ≤ r, output composite. - If n ≤ r, output prime.
- For a = 1 to
do
- if (X+a)n≠ Xn+a (mod Xr − 1,n), output composite;
- Output prime.
Here or(n) is the multiplicative order
Multiplicative order
In number theory, given an integer a and a positive integer n with gcd = 1, the multiplicative order of a modulo n is the smallest positive integer k withThe order of a modulo n is usually written ordn, or On.- Example :To determine the multiplicative order of 4 modulo 7, we compute 42 = 16 ≡ 2 ...
of n modulo
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
r, log is the binary logarithm
Binary logarithm
In mathematics, the binary logarithm is the logarithm to the base 2. It is the inverse function of n ↦ 2n. The binary logarithm of n is the power to which the number 2 must be raised to obtain the value n. This makes the binary logarithm useful for anything involving powers of 2,...
, and
is Euler's totient functionEuler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
of r.
If n is a prime number, the algorithm will always return prime: since n is prime, steps 1 and 3 will never return composite. Step 5 will also never return composite, because (2) is true for all prime numbers n. Therefore, the algorithm will return prime either in step 4 or in step 6.
Conversely, if n is composite, the algorithm will always return composite: if the algorithm returns prime, then this will occur in either step 4 or step 6. In the first case, since n ≤ r, n has a factor a ≤ r such that 1 < gcd(a,n) < n, which will return composite. The remaining possibility is that the algorithm returns prime in step 6. The authors' article proves that this will not happen because the multiple equalities tested in step 5 are sufficient to guarantee that the output is composite.
External links
- R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (PDF)
- Article by Borneman, containing photos and information about the three Indian scientists (PDF)
- Andrew Granville: It is easy to determine whether a given integer is prime
- JAVA implementation of the AKS Primality Test algorithm.
- The Prime Facts: From Euclid to AKS, by Scott AaronsonScott AaronsonScott Joel Aaronson is a theoretical computer scientist and faculty member in the Electrical Engineering and Computer Science department at the Massachusetts Institute of Technology.-Education:...
(PDF) - The PRIMES is in P little FAQ by Anton Stiglic
- 2006 Gödel Prize Citation
- 2006 Fulkerson Prize Citation
- The AKS "PRIMES in P" Algorithm Resource