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

확률론적 방법을 이용해서 나온 결과가 합성수이면 어떤 자연수 N은 합성수이지만, 결과가 소수로 나왔다고 해서 '''반드시''' 소수가 되지는 않는다. 따라서 어떤 자연수 N을 대입했을 때 나온 결과가 소수이면 이 수는 [[확률적 소수]]이다가 된다.

을 만족하는 자연수 <math>a_p</math>가 A의 모든 소인수에 대하여 존재한다면 N은 소수가 된다. 만약 첫 번째 식의 값이 1이 아니거나 두 번째 식의 값이 1 또는 N이 아니라면 N은 합성수가 된다. 또한 브릴하트와 레머, 그리고 셀프리지는 A 부분이 <math>(N/2)^{\frac{1}{3}}</math>보다 커도 사용할 수 있는 개량된 알고리즘을 개발하였으며, 이 소수판별법과 [[쇼어 알고리즘|쇼어의 알고리즘]]을 [[양자 컴퓨터|양자컴퓨터]]에서 [[재귀]] 반복하여 사용한다면 어떤 수를 소인수분해하는 데 걸리는 시간은 <math>O((\log{n})^2(\log{\log{n}})(\log{\log{\log{n}}}))</math>이 된다.

[[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>이 되며, 실행 시간이 다항 시간이기는 하지만 다른 소수판별법들보다 현저히 느리기 때문에 이 알고리즘은 실제로 큰 수를 소수판별할 때 많이 쓰이지 않는다.