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 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 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.

In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work. 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. Step 5 is also correct: since (2) is true for any choice of a coprime to n and r if n is prime, an inequality means that n must be composite.

For AKS primality test, the abstraction is narrower than the article's general subject matter: a positive case must preserve 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". Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in number-theoretic algorithms, which is why this identity is domain-specific rather than prime.

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.

Structural Signature

Sig role-phrases:

  • Defining carrier — The maximum running time of the algorithm can be bounded by a polynomial over the number of digits in the target number.
  • Constitutive relation — 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.
  • Operating condition — Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.
  • Recognition evidence — Agrawal, Kayal and Saxena proposed a variant which would run in \tilde{O}(\log(n)^{3}) if Agrawal's conjecture were true; however, a heuristic argument by Pomerance and Lenstra suggested that it is probably false.
  • Admissible variation — Similarly the comparison in step 4 can be replaced by having the trial division return prime once it has checked all values up to and including \left\lfloor \sqrt{n} \right\rfloor.
  • Characteristic consequence — The essential reduction in complexity (from exponential to polynomial) is achieved by performing all calculations in the finite ring.
  • Failure boundary — Most later improvements made to the algorithm have concentrated on reducing the size of r , which makes the core operation in step 5 faster, and in reducing the size of s the number of loops performed in step 5.

What It Is Not

  • Not the whole field of number-theoretic algorithms. The node requires the specific identity stated by 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".
  • Not an over-broad reading. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four.
  • Not an over-broad reading. 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.
  • Not an over-broad reading. The algorithm is guaranteed to distinguish deterministically whether the target number is prime or composite.
  • Not automatically Miller–Rabin primality test. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application

AKS primality test applies literally inside number-theoretic algorithms wherever the source-defined carrier and relation can be established. Its documented habitats include:

  • 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 , \log_2 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.
  • Importance. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four.

Outside number-theoretic algorithms, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Evaluation or should be marked as analogy.

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 Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The strongest recognition evidence in the frozen account is: Agrawal, Kayal and Saxena proposed a variant which would run in \tilde{O}(\log(n)^{3}) if Agrawal's conjecture were true; however, a heuristic argument by Pomerance and Lenstra suggested that it is probably false. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four. so that a reader can reproduce the classification rather than infer it from topical resemblance.

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 all calculations in the finite ring. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

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. Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.
  4. Demand recognition evidence. Agrawal, Kayal and Saxena proposed a variant which would run in \tilde{O}(\log(n)^{3}) if Agrawal's conjecture were true; however, a heuristic argument by Pomerance and Lenstra suggested that it is probably false.
  5. Test variation. Change an implementation or setting while preserving similarly the comparison in step 4 can be replaced by having the trial division return prime once it has checked all values up to and including \left\lfloor \sqrt{n} \right\rfloor.
  6. Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
  7. Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Evaluation.

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. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples

Canonical

For example, the Lucas–Lehmer test works only for Mersenne numbers, while Pépin's test can be applied to Fermat numbers only. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → 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"; recognition evidence → Agrawal, Kayal and Saxena proposed a variant which would run in \tilde{O}(\log(n)^{3}) if Agrawal's conjecture were true; however, a heuristic argument by Pomerance and Lenstra suggested that it is probably false

Applied / In Practice

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 applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Importance; invariant → 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"; boundary → the case exits the class when previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four

Structural Tensions

T1 — Stable identity versus admissible variation. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. 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 tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. The algorithm is guaranteed to distinguish deterministically whether the target number is prime or composite. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. The correctness of AKS is not conditional on any subsidiary unproved hypothesis. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. The maximum running time of the algorithm can be bounded by a polynomial over the number of digits in the target number. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate AKS primality test literally, co-instantiate Evaluation, or only resemble it?

T6 — Autonomy versus reduction. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does AKS primality test distinguish that the broader parent Evaluation leaves together?

Structural–Framed Character

AKS primality test is mixed or framed-leaning. Its structural side is the repeatable organization summarized by 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". Its framed side is the number-theoretic algorithms vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Evaluation. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent

What is skeletal. 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 stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: The maximum running time of the algorithm can be bounded by a polynomial over the number of digits in the target number. 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. It further constrains recognition and variation through: Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm. Agrawal, Kayal and Saxena proposed a variant which would run in \tilde{O}(\log(n)^{3}) if Agrawal's conjecture were true; however, a heuristic argument by Pomerance and Lenstra suggested that it is probably false.

What is domain-bound. number-theoretic algorithms supplies the operative entities, technical vocabulary, warrants, and exceptions that make AKS primality test literal. Its documented scope includes the condition that While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a galactic algorithm. Another bounded application condition is that The AKS algorithm can be used to verify the primality of any general number given. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—Similarly the comparison in step 4 can be replaced by having the trial division return prime once it has checked all values up to and including \left\lfloor \sqrt{n} \right\rfloor.—and future graph densification may discover a defensible relation only if it preserves that boundary.

This entry is a kind of Algorithm.

  • Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for AKS primality test. The reviewed identity 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 Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
  • Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

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

Not to Be Confused With

  • Evaluation. The parent omits the specialist differentia. Tell: Can the case establish 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"?
  • Miller–Rabin primality test. A randomized strong-probable-prime test that repeatedly checks modular-power witnesses and bounds the chance that a composite integer passes all selected bases. Tell: Which entry's carrier, operation, and failure condition are satisfied?
  • Integer factorization. The decomposition of a positive integer into integer factors, canonically into a unique multiset of primes up to ordering, with computational difficulty depending strongly on input size and structure. Tell: Which entry's carrier, operation, and failure condition are satisfied?
  • Cyclotomic polynomial. The monic irreducible integer polynomial whose roots are exactly the primitive nth roots of unity. Tell: Which entry's carrier, operation, and failure condition are satisfied?
  • A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would AKS primality test remain present if the detector or downstream effect changed?
  • A metaphorical analogue. A similar shape outside number-theoretic algorithms lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Evaluation?

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/AKS_primality_test (revision 1370285204).
  • Preserved source candidate: http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
  • Preserved source candidate: https://www.ams.org/bull/2005-42-01/S0273-0979-04-01037-7/home.html
  • Preserved source candidate: http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf
  • Preserved source candidate: http://www.math.dartmouth.edu/~carlp/aks041411.pdf
  • Preserved source candidate: https://web.archive.org/web/20120225052810/http://www.math.dartmouth.edu/~carlp/aks041411.pdf
  • Preserved source candidate: https://cr.yp.to/papers/aks.pdf
  • Preserved source candidate: https://web.archive.org/web/20140219064936/http://www.dm.unito.it/~cerruti/ac/aks-crandall.pdf
  • Preserved source candidate: https://www.ams.org/notices/200305/fea-bornemann.pdf

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.