소수판별법: 두 판 사이의 차이

[[AKS 소수판별법]] (Agrawal-Kayal-Saxena Primality Test, Cyclotomic AKS Test)은 결정론적이고, 무조건적이고, 모든 자연수에 대해 작동하고, 어떤 수가 소수인지 합성수인지를 다항 시간 안에 판별할 수 있는 유일한 알고리즘이다. 2002년에 발견되었으며, 이 발견을 한 세 저자들은 2006년 괴델상, [[풀커슨상]]을 비롯한 많은 상들을 수상하였다. 원래 버전의 AKS 소수판별법은 어떤 수가 소수인지 합성수인지를 <math>O(\log^{12}{n})</math>시간 안에 판별할 수 있으며, 후에 포머런스와 렌스트라에 의해 <math>O(\log^6{n})</math>시간만에 어떤 수가 소수인지 합성수인지를 확인할 수 있는 개선된 AKS 소수판별법이 나오게 되었다. 또한 이 소수판별법은소수판별법의 개량된 방법 중 하나는 아그라왈의 추측이 맞다면 실행 시간이 <math>O(\log^3n)</math>이 되며, 실행 시간이 다항 시간이기는 하지만 다른 소수판별법들보다 현저히 느리기 때문에 이 알고리즘은 실제로 큰 수를 소수판별할 때 많이 쓰이지 않는다.