Summary of “PRIMES is in P” and Its Context
1. Background and Motivation
・Primality testing—determining whether a number is prime or composite—is a central problem in mathematics and cryptography.
・Naive trial division up to $\sqrt{n}$ requires $\Omega(\sqrt{n})$ steps, far too slow for large numbers.
・An efficient algorithm must run in polynomial time with respect to the input size, $\log n$.
・Since the 1970s, the problem was known to lie in $\mathbf{NP} \cap \mathbf{co\text{-}NP}$, but a fully deterministic polynomial-time algorithm was elusive.
2. Historical Developments
・Miller (1975): Provided a deterministic polynomial-time test assuming the Extended Riemann Hypothesis (ERH).
・Rabin (1980): Made the test unconditional but randomized, creating a probabilistic primality test.
・Adleman–Pomerance–Rumely (1983): Produced a deterministic algorithm running in $(\log n)^{O(\log \log \log n)}$ time.
・The long-term goal was an unconditional deterministic polynomial-time algorithm—finally achieved by AKS.
3. Core Insight of the AKS Algorithm
・Built upon a generalization of Fermat’s Little Theorem: for prime $p$, $a^{p-1} \equiv 1 \pmod p$.
・AKS uses the congruence:
$$(X + a)^n \equiv X^n + a \pmod n$$
・Directly checking this identity is too costly ($\Omega(n)$), so AKS checks it modulo $X^r - 1$ for a small, carefully chosen integer $r$.
・The test verifies the congruence for multiple small $a$ values.
4. Steps of the Algorithm
-
Check for perfect powers: Determine if $n = a^b$ for $b > 1$.
-
Find minimal $r$: Choose the smallest $r$ such that the order of $n$ modulo $r$, $o_r(n)$, exceeds $\log^2 n$.
・Such an $r$ always exists with $r \leq \max{3, \lfloor \log^5 n \rfloor}$. -
Verify polynomial congruences:
・Check $(X+a)^n \equiv X^n + a \pmod{X^r - 1, n}$ for $a = 1$ to $\ell = \lfloor \sqrt{\phi(r) \log n} \rfloor$.
5. Mathematical Foundations
・The concept of introspective polynomials:
$$[f(X)]^m \equiv f(X^m) \pmod{X^r - 1, p}$$
・These are closed under multiplication, ensuring structural stability in the proof.
・Two algebraic groups underpin the correctness proof:
・$\mathbf{G}$ (number residues) with size $t > \log^2 n$
・$\mathbf{\mathcal{G}}$ (polynomial residues), for which Hendrik Lenstra Jr. provided a lower bound.
・The proof shows that if the algorithm outputs PRIME, then $n$ must be a power of a prime.
6. Complexity and Improvements
・Original asymptotic complexity: $O\sim(\log^{21/2} n)$, dominated by the polynomial checks.
・Improved to $O\sim(\log^{15/2} n)$ using sieve theory (primes with large $P(q-1)$).
・Under the Sophie-Germain Prime Density Conjecture, the heuristic complexity drops to $O\sim(\log^6 n)$.
・A refined Lenstra–Pomerance version achieves a provable $O\sim(\log^6 n)$ bound.