The AKS primality test (statement)

Setup. Given $n$, find small $r$ such that $\operatorname{ord}_r(n)>\log^2 n$, and check that $\gcd(a,n)=1$ for all $a\le r$.

Test. For each $a\le\lfloor\sqrt{\varphi(r)}\log n\rfloor$, check
$$(X+a)^n\equiv X^n+a\pmod{X^r-1,n}.$$
If all hold, $n$ is prime; otherwise composite.

Significance. First deterministic polynomial-time primality test (Agrawal–Kayal–Saxena, 2002). Complexity $O(\log^{6+\epsilon}n)$.

Conclusion. AKS proved that primality testing is in P.