AKS Primality

A prime number is one divisible only by 1 and itself: 2, 3, 5, 7, 11, … The question "is n prime?" is as old as mathematics itself.

Trial division — try every divisor up to $\sqrt{n}$ — works, but it is brutally slow: a 300-digit number would take longer than the age of the universe. For centuries, faster tests existed but each carried a catch: they either relied on randomness (they could be wrong with tiny probability) or on unproven conjectures (they were fast only if some unsettled hypothesis held).

The dream was a test that is:

• Deterministic — always gives the right answer, no coin flips,
• Unconditional — no unproven assumptions needed,
• Polynomial — runs in time $\text{poly}(\log n)$, the number of digits of $n$.

In August 2002, Manindra Agrawal, Neeraj Kayal and Nitin Saxena — a professor and two undergraduate students at IIT Kanpur — posted a twelve-page paper titled "PRIMES is in P". They had achieved all three goals at once.

The heart of AKS is a polynomial congruence: for a carefully chosen $r$, the number $n$ is prime if and only if

$$(x + a)^n \equiv x^n + a \pmod{n, x^r - 1}$$

holds for every $a$ from 1 to $\lfloor\sqrt{\varphi(r)}\log n\rfloor$. The demo below lets you pick a small $n$ and a single $a$, then expands both sides of the congruence mod $n$ (working in $\mathbb{Z}/n\mathbb{Z}[x]/(x^r-1)$) and tells you whether they match.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>n = <input id="inp-n" type="number" min="2" max="30" value="7"></label>
  <label>a = <input id="inp-a" type="number" min="1" max="29" value="1"></label>
  <label>r = <input id="inp-r" type="number" min="2" max="10" value="3" title="{{title_r}}"></label>
</div>
<button id="btn-check" type="button">{{btn_check}}</button>
<button id="btn-sweep" type="button">{{btn_sweep}}</button>
<button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
<div id="result" class="result"></div>
<div id="detail" class="detail"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .8rem; align-items: center; }
label { font-weight: 600; font-size: .92rem; }
input[type=number] {
  width: 62px; padding: .28rem .4rem; border: 1px solid #adb1b8;
  border-radius: 6px; font: inherit; font-size: .95rem; margin-left: .3rem;
}
button {
  font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff;
  border-radius: 8px; cursor: pointer; margin-right: .4rem; margin-bottom: .5rem;
}
button.ghost { background: #fff; color: #1d3557; }
.result {
  margin-top: .7rem; font-weight: 700; font-size: 1rem;
  min-height: 1.5em; padding: .4rem .6rem; border-radius: 6px;
}
.result.prime { background: #d4edda; color: #0a7d33; }
.result.composite { background: #f8d7da; color: #c92f3c; }
.result.info { background: #e8eef3; color: #1d3557; }
.detail { margin-top: .6rem; font-size: .83rem; color: #555; line-height: 1.6; max-height: 160px; overflow-y: auto; }
.detail code { background: #f0f3f5; border-radius: 3px; padding: 0 3px; font-size: .85em; }
.sweep-row { display: flex; gap: .3rem; flex-wrap: wrap; margin-top: .4rem; }
.badge {
  display: inline-block; padding: .15rem .45rem; border-radius: 4px;
  font-size: .78rem; font-weight: 700;
}
.badge.ok { background: #d4edda; color: #0a7d33; }
.badge.fail { background: #f8d7da; color: #c92f3c; }

// Code not found

Notice the asymmetry. Checking one congruence is fast — just polynomial arithmetic. Verifying all required $a$ values is where the polynomial bound comes from. For a composite $n$, at least one value of $a$ will expose a mismatch; for a prime, every value always matches — no guessing, no randomness. See also numbers for the deeper role primes play in computation.

Status: proven polynomial — PRIMES is in P (Agrawal, Kayal, Saxena, 2002).

Before AKS the best unconditional deterministic test ran in sub-exponential time — better than brute force, but still not polynomial. Probabilistic tests like Miller–Rabin were fast but not proven deterministic; the elliptic-curve method was fast conditionally on the Generalized Riemann Hypothesis.

AKS changed all of that:

• The core idea: a number $n$ is prime if and only if the polynomial identity $(x+a)^n \equiv x^n + a \pmod{n}$ holds in $\mathbb{Z}[x]$. This follows from the binomial theorem — for a prime $p$, every interior binomial coefficient $\binom{p}{k}$ is divisible by $p$.
• The efficiency trick: testing the identity in the full ring $\mathbb{Z}[x]$ would require computing degree-$n$ polynomials — too slow. AKS works modulo $x^r - 1$ for a small $r = O((\log n)^2)$, which keeps polynomial degrees bounded.
• The original bound: $\tilde{O}((\log n)^{12})$ — polynomial in the number of digits.
• Improved by Lenstra and Pomerance (2005): $\tilde{O}((\log n)^6)$, assuming the Sophie Germain conjecture (or unconditionally with a slightly larger constant).
• In practice: RSA cryptography uses probabilistic Miller–Rabin (which is faster in practice), but AKS matters because it proves the problem is easy in theory — no randomness, no open conjectures.

The result sits inside P vs NP: PRIMES was already known to be in co-NP (non-primality is easy to certify) and was shown to be in NP by Pratt (1975). AKS placed it in the intersection $\text{P} = \text{P}$, confirming the intuition that primality is "not fundamentally hard."

Knowing whether a number is prime is not an academic curiosity — it sits at the foundation of modern cryptography and number theory:

• RSA encryption: key generation requires large primes (typically 1024–4096 bits). Every time you visit an HTTPS website, a primality test has been run behind the scenes.
• Digital signatures and certificates: the same large primes underpin certificate authorities and the entire public-key infrastructure.
• Pseudorandom number generation: many generators use prime moduli for guaranteed full-period behavior.
• Theoretical landmark: AKS resolved a long-standing open question and demonstrated that a famous-looking hard problem can fall to an unexpected elementary idea. It inspired a generation of researchers to look again at other "intractable" number-theory problems.
• Complexity theory: AKS confirmed PRIMES ∈ P, clarifying the landscape between P and NP. The techniques — polynomial identities over rings, character sums — crossed over into other hardness proofs.

In practice the faster (but probabilistic) Miller–Rabin test is used in production crypto libraries. But the existence of AKS matters: it tells us that primality is not an intrinsic source of hardness, and so RSA's security must come from factoring, not testing. See factoring for why the reverse direction remains wide open.

For two millennia, no one knew whether deciding "is $n$ prime?" required more than polynomial work. Randomized algorithms came close; conditional results assumed big conjectures. Then in 2002, a professor and two undergraduates at IIT Kanpur wrote twelve pages and settled it: PRIMES is in P.

The proof used nothing exotic — binomial coefficients, polynomial arithmetic, a clever choice of modulus. The simplicity is the message: an ancient-sounding hard problem can fall to a neat algebraic observation, and what looked like an insurmountable barrier was really just waiting for the right angle.

AKS did not break RSA — the security of factoring is a different story and still stands. But it drew a clean line: testing primality is easy, factoring is (believed to be) hard, and P vs NP remains the great unanswered question underneath them both.