AKS primality test
From orig
(Redirected from AKS)
Jump to navigationJump to searchThis article is under development by Optim.
Suggested titles: AKS primality test, AKS Primality Test, AKS algorithm, AKS, Agarwal Kayal Saxena algorithm, Agarwal Kayal Saxena primality test, Agarwal Kayal Saxena, Cyclotomic AKS test
The Agarwal Kayal Saxena algorithm, also called AKS algorithm, is a deterministic primality-proving algorithm discovered by three Indian scientists in August 2002. It determines whether a number is prime or composite and runs in polynomial time.
AKS has a key difference with all previous general primality-proving algorithms: It does not require any unproven hypothesis (such as RH) to be true in order to have provable polynomial time on all inputs.