Skip to content

AKS primality test

The AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm 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".

Version
v1 · 2026-09-28 · History
Domain-specific #
7911
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Number Theoretic Algorithms, Computational Complexity → Computer Science & Software Engineering

Core Idea

AKS primality test is treated here as the recurring number-theoretic algorithms identity summarized by this source-grounded definition: The AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm 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 AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm.

How would you explain it like I'm…

The Always-Sure Prime Checker

A prime number is one you can only split evenly by 1 and itself, like 7. The AKS primality test is a recipe that always tells you for sure whether a number is prime, never just guessing. And it stays fast enough even when the numbers get really, really big.

The Fast, Certain Prime Test

A prime number can only be divided evenly by 1 and itself. Checking whether a giant number is prime by trying every divisor would take far too long. In 2002, three computer scientists in India, Agrawal, Kayal, and Saxena, published the AKS primality test, a step-by-step method that always gives a correct yes-or-no answer. It was the first method proven to do this in 'polynomial time,' which means the work grows reasonably as the number gets longer, and the proof didn't depend on any unproven math guesses. Their paper was called 'PRIMES is in P.'

Deterministic Polynomial-Time Primality Proof

The AKS primality test, published in 2002 by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of IIT Kanpur in a paper titled "PRIMES is in P", is a deterministic algorithm that proves whether a number is prime or composite. 'Deterministic' means it uses no randomness and never gives a probably-right answer. Its big result was running in polynomial time in the number of digits, for every input, without relying on unproven conjectures such as the generalized Riemann hypothesis. Other methods like ECPP and APR also prove primality for sure, but they are not known to be polynomial time for all inputs. The core check uses the fact that primes satisfy a certain polynomial identity; if the identity fails, the number must be composite. The authors received the Gödel Prize and the Fulkerson Prize in 2006.

 

The AKS primality test (Agrawal–Kayal–Saxena, also called the cyclotomic AKS test) is a deterministic primality-proving algorithm published in 2002 in 'PRIMES is in P'. It was the first algorithm shown to decide primality in polynomial time unconditionally, that is, without assuming conjectures such as the generalized Riemann hypothesis, and its proof notably avoids analysis. It rests on a polynomial congruence that holds for every choice of a coprime to n and a parameter r whenever n is prime; if the congruence fails for some tested a, n must be composite. This places the problem PRIMES in the complexity class P. By contrast, ECPP and APR are also certifying tests but lack known polynomial bounds on all inputs. The result earned the 2006 Gödel and Fulkerson Prizes.

Scope of Application

  • Importance. While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a galactic algorithm.

  • Importance. The AKS algorithm can be used to verify the primality of any general number given.

  • Importance. Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.

  • The algorithm. Here \operatorname{ord}r(n) is the multiplicative order of n modulo r , \log2 is the binary logarithm, and \varphi® is Euler's totient function of r .

  • Importance. AKS is the first primality-proving algorithm to be simultaneously general, polynomial-time, deterministic, and unconditionally correct.

Clarity

A clear use of AKS primality test names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is The AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of.

Manages Complexity

AKS primality test compresses multiple number-theoretic algorithms details into a stable diagnostic relation. The source shows both the central mechanism—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-unproved generalized Riemann hypothesis.—and the practical consequence—the essential reduction in complexity (from exponential to polynomial) is achieved by performing.

Abstract Reasoning

  1. Type the carrier. Identify the number-theoretic algorithms entities to which the claim applies.
  2. State the relation. Use the source-grounded identity: The AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm 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".
  3. Check operation and conditions.

Knowledge Transfer

Within the home domain. Knowledge about AKS primality test transfers literally when a new case preserves the same carrier type, relation, and recognition test. While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a galactic algorithm. The AKS algorithm can be used to verify the primality of any general number given. Beyond the home domain. No canonical parent is asserted for AKS primality test.

Relationships to Other Abstractions

Local relationship map for AKS primality testParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.AKS primality testDOMAINPrime abstraction: Algorithm — is a kind ofAlgorithmPRIME

Current abstraction AKS primality test Domain-specific

Parents (1) — more general patterns this builds on

  • AKS primality test is a kind of Algorithm Prime

    AKS is a deterministic finite procedure for deciding primality.

Hierarchy paths (2) — routes to 2 parentless roots

Neighborhood in Abstraction Space

AKS primality test sits in a sparse region of the domain-specific corpus (65th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Number-Theoretic Properties & Tests (20 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08