Description
AKS: First unconditional deterministic polynomial-time primality test. Key: n is prime iff (X+a)^n ≡ X^n+a (mod n, X^r−1) for small a. Steps: (1) n perfect power? (2) find small r with ord_r(n) > log² n; (3) check small a; (4) n ≤ r ⇒ prime. Time Õ(log^6 n). Landmark 2002 result.
See also: Fermat, Miller–Rabin, Sieve
Algorithm Flowchart
graph TD
A["Input: n"]
B["n = a^b? → composite"]
C["Find r: ord_r n > log² n"]
D["a ≤ r: gcd a,n > 1? → composite"]
E["For a=1 to ⌊√φ r log n⌋:\n(X+a)^n ≡ X^n+a mod n,X^r−1?"]
F["Composite"]
G["Prime"]
A --> B
B --> C
C --> D
D --> E
E -->|No| F
E -->|Yes| G
classDef red fill:#ff6b6b,color:#fff
classDef green fill:#51cf66,color:#fff
classDef lavender fill:#e6e6fa,color:#333
class A red
class B,C,D,E,G green
class E lavender
class F red
See also
Fermat Primality Test · Miller–Rabin · Extended Euclidean (for modular arithmetic)