# AKS primality test For centuries the problem of deciding if a number $N$ is prime was considered hard and no efficient algorithm was known but in 2002 Manindra Agrawal, Neeraj Kayal, and Nitin Saxena published a polynomial algorithms proving that $\text{PRIMES}\in P$[^1] . The algorithm is based on validating a **necessary** primality test for a fixed number of trials and if all pass conclude that $N$ is prime. This is a remarkable as AKS turns a necessary property of primes into a property that is also **sufficient**. AKS is the first primality-proving algorithm to be simultaneously _general_, _polynomial-time_, _deterministic_, and _unconditionally correct_[^3] - AKS works for any $N$ while other algorithms work for numbers with certain properties. - AKS runtime is polynomial while for other algorithms it is not known if they will complete in polynomial time for all numbers. - AKS guarantee to output either $N$ is prime or not correctly. - AKS correctness is not conditioned on any unproven conjecture while the deterministic version of [[Miller-Rabin primality test]] assume yet-unproved generalized Riemann hypothesis. Here is a summary of the algorithm[^2] ![[Pasted image 20260626132406.png|620]] It is less efficient than statistical algorithms for primality like [[Miller-Rabin primality test]] but it provides a decisive result of primality while statistical algorithms are statistic and not decisive. This means that when primality is crucial, it make sense to generate candidates with fast statistically algorithms and then validate primality with AKS. ## Created 2026-06-26 12:54 [^1]: Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. “PRIMES is in P.” _Annals of Mathematics_, vol. 160, no. 2, 2004, pp. 781–793. https://doi.org/10.4007/annals.2004.160.781 [^2]: Vijay Menon. _Deterministic Primality Testing_. arXiv:1311.3785 [cs.CC], 2013. [^3]: https://en.wikipedia.org/wiki/AKS_primality_test