Editing AKS primality test (section)

==Importance==
AKS is the first primality-proving algorithm to be simultaneously ''general'', ''polynomial-time'', ''deterministic'', and ''unconditionally correct''. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four. 
* The AKS algorithm can be used to verify the primality of any '''general''' number given. Many fast primality tests are known that work only for numbers with certain properties. For example, the [[Lucas–Lehmer primality test|Lucas–Lehmer test]] works only for [[Mersenne number]]s, while [[Pépin's test]] can be applied to [[Fermat number]]s only.
* The maximum running time of the algorithm can be bounded by a '''[[Polynomial time#Polynomial time|polynomial]]''' over the number of digits in the target number. [[Elliptic curve primality proving|ECPP]] and [[Adleman–Pomerance–Rumely primality test|APR]] conclusively prove or disprove that a given number is prime, but are not known to have polynomial time bounds for all inputs.
* The algorithm is guaranteed to distinguish '''[[Deterministic algorithm|deterministically]]''' whether the target number is prime or composite. Randomized tests, such as [[Miller–Rabin primality test|Miller–Rabin]] and [[Baillie–PSW primality test|Baillie–PSW]], can test any given number for primality in polynomial time, but are known to produce only a probabilistic result.
* The correctness of AKS is '''not conditional''' on any subsidiary unproven [[hypothesis]]. In contrast, Miller's version of the [[Miller–Rabin primality test#Deterministic variants|Miller–Rabin test]] is fully deterministic and runs in polynomial time over all inputs, but its correctness depends on the truth of the yet-unproven [[generalized Riemann hypothesis]].

While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a [[galactic algorithm]].  For 64-bit inputs, the [[Baillie–PSW primality test|Baillie–PSW test]] is deterministic and runs many orders of magnitude faster.  For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is ''far'' superior to AKS.  Additionally, ECPP can output a [[primality certificate]] that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.