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

=== AKS 소수판별법 ===

[[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 소수판별법이 나오게 되었다.

{{수론 알고리즘}}

[[분류:소수 판별법| ]]