AKS 소수판별법

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

AKS 소수판별법은 어떤 자연수소수인지 판별하는 결정론적 알고리즘이다. 2002년 8월 6일, 인도 칸푸르 공과대학의 컴퓨터 과학자 마닌드라 아그라왈, 니라지 카얄, 니틴 삭세나가 공동으로 출판한 논문 "PRIMES is in P"[1]에서 처음으로 발표되었다.

세 저자는 이 연구로 2006년 괴델상, 풀커슨상을 포함 각종 상을 수상하였다.

중요성[편집]

AKS 소수판별법은 최초로 발견된 일반적이고, 무조건적이고, 결정론적다항 시간 알고리즘이다. 4가지 가운데 3가지 특성을 가진 알고리즘은 존재했으나, 4가지 특성을 모두 가진 것은 AKS가 최초이다.

개요[편집]

AKS 소수판별법은 다음과 같은 정리를 이용한다

정수 n (≥ 2) 은, n서로소인 모든 정수 a에 대해 다음 합동식이 성립할때만 소수이며, 그렇지 않으면 합성수이다.

(x - a)^{n} \equiv (x^{n} - a) \pmod{n} \qquad (1)

위 항등식에서 x자유 변수이며, (x-a)^{n}을 풀었을 때 좌변과 우변의 모든 계수가 일치해야 한다.[1]

위 정리는 페르마의 소정리다항식에 대해 일반화한 것으로, 다음 정리를 이용하여 쉽게 증명할 수 있다.

0<k<n인 모든 k에 대해 {n \choose k} \equiv 0 \pmod{n}이면, n은 소수이며, 그렇지 않으면 합성수이다.

정리 (1)은 그 자체로 소수판별법이지만, 모든 정수에 대해 이 관계를 검증하는 것은 지수 시간 알고리즘이다. 이 방법의 시간복잡도를 줄이기 위해, AKS 알고리즘은 다음 합동식을 이용한다.

(x - a)^{n} \equiv (x^{n} - a) \pmod{(n,x^{r}-1)} \qquad (2)

위 식은 다음 명제와 같은 의미를 갖는다.

(x - a)^n - (x^n - a) = nf + (x^r - 1)g를 만족하는 다항식 fg가 존재한다.

r의 크기가 n의 자리수에 대해 로그 복잡도를 가지므로, 다항식 fg의 존재를 찾는 것은 다항 시간 안에 완료할 수 있다.

알고리즘[편집]

AKS 알고리즘의 개요는 다음과 같다.

1보다 큰 정수 n을 입력으로 받는다.
  1. n=a^b인 정수 a > 0 와 b > 1 가 존재하면, 합성수를 출력한다.
  2. o_{r}(n) > \log^{2}(n)을 만족하는 가장 작은 r을 찾는다.
  3. 만약 ar이고 1 < gcd(a, n) < n 을 만족하는 정수 a가 존재하면, 합성수를 출력한다.
  4. 만약 nr이면 소수를 출력한다.
  5. 1에서 \scriptstyle\lfloor \scriptstyle{\sqrt{\varphi(r)}\log(n)} \scriptstyle\rfloor까지의 모든 정수 a에 대해,
    (x+a)^{n} \neq x^{n}+a \pmod{x^{r}-1, n}이면, 합성수를 출력한다.
  6. 소수를 출력한다

위 알고리즘에서 or(n)은 곱의 차수, 즉 n^{k} \equiv 1 \pmod{r}을 만족하는 가장 작은 k이다. log는 이진 로그 함수이고, \phi (r)오일러 피 함수이다.

주석[편집]

  1. Agrawal, Manindra (2004년). PRIMES is in P. 《수학연보》 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.

참고문헌[편집]