AKS primality test

From orig
Jump to navigationJump to search

This 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.

See also[edit | edit source]

External links[edit | edit source]