AKS 소수판별법

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

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

중요성[편집]

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

  • 일반적: AKS 알고리즘은 모든 자연수에 대해 그 수가 소수인지 합성수인지를 판별할 수 있다. 속도가 빠른 기존의 소수 판별 알고리즘들은 몇몇 특징을 가진 소수에 대해서만 작동하였다.

예를 들어 루카스-레머 소수판별법메르센 소수에 대해서만 동작하며, 루카스-레머-리젤 소수판별법k ⋅ 2n − 1(k는 홀수)인 수에 대해서만 작동하고, 페팽 소수판별법페르마 수에 대해서만 동작한다.

개요[편집]

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

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

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

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

인 모든 k에 대해 이면, n은 소수이며, 그렇지 않으면 합성수이다.

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

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

를 만족하는 다항식 fg가 존재한다.

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

알고리즘[편집]

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

1보다 큰 정수 n을 입력으로 받는다.
  1. 인 정수 a > 1 와 b > 1 가 존재하면, 합성수를 출력한다.
  2. 을 만족하는 가장 작은 r을 찾는다.
  3. 만약 ar이고 1 < gcd(a, n) < n 을 만족하는 정수 a가 존재하면, 합성수를 출력한다.
  4. 만약 nr이면 소수를 출력한다.
  5. 1에서 까지의 모든 정수 a에 대해,
    이면, 합성수를 출력한다.
  6. 소수를 출력한다

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

각주[편집]

  1. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). “PRIMES is in P” (PDF). 《수학연보160 (2): 781–793. JSTOR 3597229. doi:10.4007/annals.2004.160.781. 

참고문헌[편집]