KEVOS
ArticlesServicesCase studiesAboutContact
ArticlesServicesCase studiesAboutContact
← ArticlesThe AKS Algorithm and Its AnalysisEngineering · Engineering MathematicsLesson 622/883← PrevNext →
GuidePublished 7 Aug 2026Updated 13 Aug 20268 min readBy Kevin Jogin
On this page

Ask about this page

KEVOS AIThe AKS Algorithm and Its Analysis

KEVOS knowledge first · trusted web sources when needed

Engineering  /  Mathematics  — Primality Testing

The AKS Algorithm and Its Analysis

The AKS algorithm in full, its correctness argument, complexity, and why it is not used in practice.

Page KV-MATH-0395Reading time 3 minReviewed 2026-08-07Author Kevin Jogin

Executive summary

AKS assembles a perfect power check, a search for a suitable modulus r, a gcd sweep, and a bounded set of polynomial congruence checks into a deterministic polynomial-time primality test.

Its complexity is polynomial but of high degree, which is why every practical system still uses Miller-Rabin.

Learning objectives

  1. State the algorithm's steps in order.
  2. Sketch the correctness argument.
  3. Compare its complexity against the probabilistic alternative.

01The algorithm

Algorithm

AKS primality test

Inputinteger n > 1
Outputprime or composite, with certainty
  1. If n is a perfect power, report composite.
  2. Find the smallest r such that the multiplicative order of n modulo r exceeds (log₂ n)².
  3. For each a ≤ r: if 1 < gcd(a, n) < n, report composite.
  4. If n ≤ r, report prime.
  5. For each a from 1 to a bound derived from r and n:
  6.   If (X + a)^n ≢ X^n + a (mod n, X^r − 1), report composite.
  7. Report prime.
Cost  polynomial in log n; originally about (log n)^{12}, later improved

Each polynomial congruence is checked by repeated squaring in the quotient ring, so the cost is a number of polynomial multiplications proportional to log n, each on polynomials of degree below r.

02Correctness in outline

  1. Perfect powers removed

    Step 1 eliminates the case that would otherwise pass for structural reasons.

  2. Small factors removed

    Step 3 catches any n sharing a factor with some a ≤ r.

  3. Suppose n is composite and passes

    Then a certain group of residues generated by the checked congruences must be large.

  4. Derive a contradiction

    Counting the distinct polynomials the group generates exceeds the size the quotient ring permits.

The existence of a suitable r below a polynomial bound is itself a non-trivial number-theoretic estimate, and it is what keeps the polynomial degree — and hence the cost of each multiplication — under control.

Note
The proof is elementary in the technical sense: it uses no analytic number theory beyond standard estimates, which was part of what made the result surprising. The problem had been attacked with far heavier machinery for years.

03Why Miller-Rabin still wins

  1. Miller-Rabin, 40 roundsO(len(n)³) × 40Error below 2^{−80}; milliseconds at 2048 bits
  2. AKS, originalÕ(len(n)^{12})Deterministic; impractical at cryptographic sizes
  3. AKS, improved variantsÕ(len(n)^{6})Still far slower than the probabilistic test
  4. Elliptic curve primality provingHeuristically Õ(len(n)^{4})The practical choice when a certificate is required
Choosing a primality method
RequirementMethod
Fast test, error below hardware fault rateMiller-Rabin
Verifiable certificate of primalityElliptic curve primality proving
Unconditional deterministic guaranteeAKS
Small inputsTrial division against a sieved table

The practical lesson generalises beyond this case: a polynomial-time algorithm is not automatically a usable one, and asymptotic classification and engineering suitability are different questions. AKS answered a theoretical question definitively and changed no deployment.

04Frequently asked questions

Was AKS a surprise?

Considerable. The problem had resisted for decades and the techniques in use were heavy. The AKS argument is elementary and short enough to present in a lecture, which made the result striking independently of its practical impact.

Have the exponents improved since?

Yes, substantially — variants and sharper estimates for the modulus bound have brought the exponent down considerably. None of the improvements makes it competitive with Miller-Rabin.

Why use elliptic curve primality proving instead when a proof is needed?

Because it produces a certificate that a third party can verify quickly, and it is far faster in practice despite lacking an unconditional complexity bound. Where a proof must be checked rather than trusted, that is the better trade.

Related pages

  • Deterministic Primality Testing: The Basic Idea

Sources and method

Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 490-500.

This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.

Author: Kevin Jogin. Last reviewed 2026-08-07.

Handbook application: from concept to controlled practice

Purpose. This expanded section turns the original page into a practical handbook. It preserves the supplied material and adds a repeatable way to apply, check and review The AKS Algorithm and Its Analysis. It does not replace a contract, legislation, a controlled standard, competent engineering judgement or specialist advice.

The operating aim is to turn a compact mathematical statement into a usable chain of definitions, claims, examples and checks. Read the original explanation first, then use the workflow and checks below to convert knowledge into evidence.

Treat The AKS Algorithm and Its Analysis as a network of definitions and implications, not as a list of formulas. The working vocabulary on this page—algorithm, correctness, analysis, full, argument—should be made explicit before any proof or computation begins. Record the ambient set or structure, the permitted operations and the equality or equivalence relation in use. A compact theorem often changes meaning when the base field, finiteness condition, commutativity assumption or direction of an action changes.

For a proof, write the hypotheses as a checklist and mark the line at which each one is used. For a computation, state the representation of the input, the arithmetic model, the termination condition and the output invariant. For a classification problem, distinguish existence from uniqueness and distinguish an object from its representation. These separations prevent a correct local calculation from being mistaken for the general result.

A useful worked example should be small enough to inspect completely but rich enough to exercise the main mechanism. Compute the result in two ways where practical: symbolically and by substitution, structurally and numerically, or directly and through a normal form. Then include one near-miss example in which a hypothesis fails. The contrast explains why the theorem is shaped as it is and gives the reader a diagnostic pattern for later problems.

Verification is part of the mathematics. Check domains and codomains, substitute proposed solutions, test identity and zero cases, compare dimensions or cardinalities, and confirm that maps respect the required operations. In numerical work, report precision, conditioning and a residual rather than digits alone. In algorithmic work, separate mathematical correctness from implementation complexity and resource limits.

Step-by-step operating method

  1. Fix the setting. State the objects, ambient structure, notation and assumptions before manipulating symbols.
  2. Separate claims. Distinguish definitions, hypotheses, conclusions, equivalent conditions and consequences.
  3. Choose a method. Select proof, construction, calculation or algorithm according to the question actually asked.
  4. Work a small case. Use the smallest non-trivial example to expose the mechanism and test edge behaviour.
  5. Verify independently. Substitute back, check invariants, test boundary cases or use an alternative derivation.

Worked-example protocol

Illustrative method—not a source theorem. Start with a small admissible input and list the definitions it must satisfy. Carry out each transformation on a separate line, citing the property that permits it. Preserve exact values until approximation is necessary. At the end, verify the output against the original definition and one invariant such as dimension, degree, determinant, order, norm or residual. Then alter one hypothesis and observe which step ceases to be valid. This protocol creates a reusable example without inventing a theorem-specific numerical answer.

StageRecordQuality check
InputObjects, domain, notation, assumptionsEvery symbol is defined
MethodPermitted operation or cited result at each stepAll hypotheses hold
OutputExact result and representationCorrect type, domain and form
VerificationSubstitution, invariant or alternative derivationIndependent agreement
Boundary testZero, identity, degenerate or failed hypothesisScope is understood

Common failure modes and recovery actions

1. Watch for

Using a theorem without checking every hypothesis.

Recovery: Return to the governing definition or requirement and restate the decision in one sentence.

2. Watch for

Treating a suggestive example as a proof of the general case.

Recovery: Separate evidence from assumption, assign an owner and set a date for validation.

3. Watch for

Changing notation or conventions part-way through an argument.

Recovery: Run a small counterexample, boundary test, pilot or independent check before proceeding.

4. Watch for

Hiding a division-by-zero, convergence, finiteness or commutativity assumption.

Recovery: Record the consequence, decision and rationale, then update the controlled baseline.

5. Watch for

Reporting a computed result without a residual, substitution or structural check.

Recovery: Escalate when the issue affects safety, compliance, acceptance, material value or an agreed tolerance.

Review checklist

  • Can every symbol be traced to a definition or prior result?
  • Which hypothesis does each major step use?
  • Does the method cover zero, identity, degenerate and boundary cases?
  • Can the conclusion be checked by a second representation or calculation?
  • Are mandatory requirements distinguished from recommendations and illustrative values?
  • Are sources, assumptions, units, dates and versions recorded closely enough to reproduce the decision?
  • Have safety, legal, ethical, stakeholder and operational consequences been considered at the appropriate level?
  • Is there a named owner and a trigger for review, escalation, change or retirement?

Questions for deeper application

What is the most important distinction a practitioner must preserve when applying The AKS Algorithm and Its Analysis?

Answer with a fact or cited source where available. Where evidence is incomplete, record the assumption, consequence, responsible owner and next validation action.

Which assumption about algorithm would change the result most if it proved false?

Answer with a fact or cited source where available. Where evidence is incomplete, record the assumption, consequence, responsible owner and next validation action.

What evidence would allow an independent reviewer to reproduce or challenge the conclusion?

Answer with a fact or cited source where available. Where evidence is incomplete, record the assumption, consequence, responsible owner and next validation action.

Which boundary, exception or failure case has not yet been tested?

Answer with a fact or cited source where available. Where evidence is incomplete, record the assumption, consequence, responsible owner and next validation action.

What must be handed over, monitored or reviewed after the immediate work is complete?

Answer with a fact or cited source where available. Where evidence is incomplete, record the assumption, consequence, responsible owner and next validation action.

Authoritative references and use notes

The sources below were selected as institutional or primary guidance for the broader practice. They support the handbook method; they do not imply that every statement or clause in a source applies to every project. Confirm the current edition, jurisdiction, contract and application before treating any requirement as mandatory.

  • NIST Digital Library of Mathematical Functions — National Institute of Standards and Technology. Used for mathematical notation, numerical methods, asymptotics and special functions. Accessed 2026-08-13.
  • MIT OpenCourseWare — Number Theory I — Massachusetts Institute of Technology. Used for algebraic and analytic number theory. Accessed 2026-08-13.

Continue learning

Deterministic Primality Testing: The Basic IdeaGuide · Engineering MathematicsNEXT LESSON →Finding a Generator of the Group of Units Modulo pGuide · Engineering MathematicsFactoring and Computing Euler's Phi FunctionGuide · Engineering MathematicsBrute-Force Discrete Logarithm SearchGuide · Engineering Mathematics
KEVOS · Engineering, manufacturing and project improvement
ArticlesServicesCase studiesAboutContact
© 2026 KEVOS®