AKS 소수판별법 문서 원본 보기

{{위키데이터 속성 추적}}
'''AKS 소수판별법'''은 어떤 [[자연수]]가 [[소수 (수론)|소수]]인지 판별하는 [[결정론적 알고리즘]]이다. 2002년 8월 6일, [[인도 공과대학교 칸푸르]]의 컴퓨터 과학자 [[마닌드라 아그라왈]], [[니라지 카얄]], [[니틴 삭세나]]가 공동으로 출판한 논문 "PRIMES is in P"<ref name="AKS">{{저널 인용|first=Manindra |last=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |title=PRIMES is in P |journal=[[수학연보]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 }}</ref>에서 처음으로 발표되었다.

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

== 중요성 ==

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

* 일반적: AKS 알고리즘은 ''모든'' 자연수에 대해 그 수가 소수인지 합성수인지를 판별할 수 있다. 속도가 빠른 기존의 소수 판별 알고리즘들은 몇몇 특징을 가진 소수에 대해서만 작동하였다.
예를 들어 [[루카스-레머 소수판별법]]은 [[메르센 소수]]에 대해서만 동작하며, [[뤼카–레머–리젤 소수판별법|뤼카-레머-리젤 소수판별법]]은 ''k'' ⋅ 2<sup>''n''</sup> − 1(k는 [[홀수와 짝수|홀수]])인 수에 대해서만 작동하고, [[페팽 소수판별법]]은 [[페르마 수]]에 대해서만 동작한다.
* [[다항 시간]]: AKS 알고리즘의 [[시간 복잡도]]는 최악의 경우에도 소수의 자리수에 대해 [[다항 시간]]안에 완료된다. [[타원곡선 소수판별법]]이나 [[APR 소수판별법]]은 모든 자연수에 대해 다항 시간 안에 완료된다는 것이 증명되지 않았다.
* [[결정론적 알고리즘|결정론적]]: AKS 알고리즘은 자연수가 소수인지 합성수인지를 결정적으로 확인할 수 있다. [[밀러-라빈 소수판별법]]이나 [[베일리-PSW 소수판별법]]은 모든 자연수에 대해 다항 시간 안에 완료되지만, 이 판별법으로 소수라는 답이 나오더라도 해당 자연수가 합성수일 확률이 존재한다.
* 무조건적: AKS 소수판별법은 증명되지 않은 가설에 기반하고 있지 않다. [[밀러 소수판별법]]은 결정론적이고, 모든 자연수에 대해 다항 시간 안에 완료되지만, 아직 증명되지 않은 [[일반화 리만 가설]]이 참일 경우에만 참이라는 것이 증명되어 있다.

== 개요 ==

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

정수 ''n'' (≥ 2) 은, ''n''과 [[서로소]]인 모든 정수 ''a''에 대해 다음 [[합동식]]이 성립할 때만 소수이며, 그렇지 않으면 합성수이다.
:<math>(x - a)^{n} \equiv (x^{n} - a) \pmod{n} \qquad (1)</math>
위 항등식에서 ''x''는 [[자유 변수]]이며, <math>(x-a)^{n}</math>을 풀었을 때 좌변과 우변의 모든 계수가 일치해야 한다.<ref name="AKS"/>

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

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

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

:<math>(x - a)^{n} \equiv (x^{n} - a) \pmod{(n,x^{r}-1)} \qquad (2)</math>

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

:<math>(x - a)^n - (x^n - a) = nf + (x^r - 1)g</math>를 만족하는 다항식 ''f''와 ''g''가 존재한다.

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

== 알고리즘 ==

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

: 1보다 큰 정수 ''n''을 입력으로 받는다.
# <math>n=a^b</math>인 정수 ''a''&nbsp;>&nbsp;1 와 ''b''&nbsp;>&nbsp;1 가 존재하면, ''합성수''를 출력한다.
# <math>o_{r}(n) > \log^{2}(n)</math>을 만족하는 가장 작은 ''r''을 찾는다.
# 만약 ''a'' ≤ ''r''이고 1&nbsp;<&nbsp;[[최대공약수|gcd]](''a'', ''n'')&nbsp;<&nbsp;''n'' 을 만족하는 정수 ''a''가 존재하면, ''합성수''를 출력한다.
# 만약 ''n'' ≤ ''r''이면 ''소수''를 출력한다. 만약 n>5690034이면 이 단계는 무시해도 된다.
# 1에서 <math>\scriptstyle\lfloor \scriptstyle{\sqrt{\varphi(r)}\log(n)} \scriptstyle\rfloor</math>까지의 모든 정수 ''a''에 대해,
#: <math>(x+a)^{n} \neq x^{n}+a \pmod{x^{r}-1, n}</math>이면, ''합성수''를 출력한다.
# ''소수''를 출력한다

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

== 예시 ==
n=31을 소수판별하고 싶다고 하자.

1. <math>31^{\frac{1}{2}}, 31^{\frac{1}{3}}, 31^{\frac{1}{4}}</math>는 모두 자연수가 아니다. (31의 1/5제곱부터는 거듭제곱들이 2 미만이 되므로 검사할 필요가 없다.)

2. r = 29이다.

3. gcd(2, 31)=1, gcd(3, 31)=1, ... , gcd(28, 31)=1, gcd(29, 31)=1이다.

4. 31>29이므로 5단계로 넘어간다.

5. <math>(x+a)^{n} \equiv x^{n}+a \pmod{x^{r}-1, n}</math>이 성립하려면 '''(A)''' <math>(x+a)^n\pmod{x^{29}-1, 31}</math>에서 '''(B)''' <math>x^n+a\pmod{x^{29}-1, 31}</math>를 뺀 값이 (mod x<sup>r</sup>''-''1, n)에서 0이어야 한다. 따라서,

'''(A)''' <math>(x+a)^{31}\equiv x^{31}+31x^{30}a+465x^{29}a^2+\cdot\cdot\cdot+465x^2a^{29}+31xa^{30}+a^{31}\pmod{x^{29}-1, 31}</math>이고, 이 전개한 식을 x<sup>29</sup>-1로 나눈 나머지는 <math>a^{31}+465a^2+(31a+31a^{30})x+(1+465a^{29})x^2+\cdot\cdot\cdot+4495a^3x^{28}</math>

가 되며 다시 이 식을 31로 나눈 나머지는 <math>a^{31}+x^2</math>가 된다. 따라서

'''(A)''' <math>(x+a)^{31}\equiv a^{31}+x^2\pmod{x^{29}-1, 31}</math>

이 되고,

'''(B)''' <math>x^{31}+a\equiv x^2+a\pmod{x^{29}-1, 31}</math>

이 된다. 여기서 '''(A) - (B)'''는

<math>a^{31}-a\equiv0\pmod{x^{29}-1, 31}</math>

이 되며, a=1부터 a=<math>\lfloor\sqrt{\varphi(29)}\log_{2}{31}\rfloor</math>=26까지의 정수들에 대하여 <math>a^{31}-a\equiv0\pmod{31}</math>이 성립하므로 조건을 만족하는 모든 a에 대하여<math>(x+a)^{n} \equiv x^{n}+a \pmod{x^{r}-1, n}</math>이 성립한다.

6. 따라서 n=31은 소수가 된다.

== 각주 ==
<references/>

== 참고 문헌 ==

* H. W. Lenstra jr. 와 Carl Pomerance, "[https://web.archive.org/web/20120225052810/http://www.math.dartmouth.edu/~carlp/aks041411.pdf Primality testing with Gaussian periods]", 2011년 4월 12일

{{수론 알고리즘}}

[[분류:소수 판별법]]
[[분류:유한체]]