AKS 소수판별법

3. 개념

AKS 소수판별법은 페르마 소정리를 다항식으로 일반화한 다음 정리에 기반한다.^[1]

정수 ''n'' (≥ 2)과 ''n''과 서로소인 임의의 정수 ''a''가 주어졌을 때, ''n''이 소수일 필요충분조건은 다음 합동식이 다항식 환 $(\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]$에서 성립하는 것이다.

:$(x\; +\; a)^\{n\}\; \backslash equiv\; x^\{n\}\; +\; a\; \backslash pmod\{n\}\; \backslash qquad\; (1)$

여기서 ''x''는 형식적인 변수이다. 이 합동식은 $(x+a)^n$을 이항 정리를 이용해 전개했을 때 ''x''의 각 차수에 해당하는 이항 계수 $\{n\; \backslash choose\; k\}$ (단, )가 모두 ''n''으로 나누어떨어짐을 의미하며, 이는 ''n''이 소수일 때 성립하는 성질이다.^[7]

합동식 (1) 자체는 소수판별법으로 사용될 수 있지만, 다항식 $(x+a)^n$을 직접 전개하여 모든 계수를 확인하는 것은 ''n''의 크기에 대해 지수 시간 복잡도를 가지므로 매우 비효율적이다.

AKS 알고리즘은 계산 시간을 줄이기 위해, 합동식 (1)을 직접 확인하는 대신 적절히 작은 정수 ''r''을 선택하여 몫 다항식 환 $(\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]/(X^r\; -\; 1)$에서 다음 합동식을 검사한다.

:$(x\; +\; a)^\{n\}\; \backslash equiv\; x^\{n\}\; +\; a\; \backslash pmod\{(n,\; x^\{r\}-1)\}\; \backslash qquad\; (2)$

이는 다항식 $x^r-1$로 나눈 나머지에 대해서만 합동 관계를 확인하는 것과 같으며, $(x\; +\; a)^n\; -\; (x^n\; +\; a)\; =\; nf\; +\; (x^r\; -\; 1)g$를 만족하는 어떤 다항식 ''f''와 ''g''가 존재한다는 의미이다.

만약 ''r''의 크기를 ''n''의 자릿수(즉, $\backslash log\; n$)에 대한 다항식 정도로 작게 선택하면, 합동식 (2)를 검증하는 것은 다항 시간 안에 완료될 수 있다. 그러나 법 $x^r-1$을 추가하면 합동 조건이 약화되어, 합성수임에도 불구하고 이 조건을 만족하는 경우가 생길 수 있다. 따라서 AKS 알고리즘은 이 판별의 정확도를 높이기 위해, 하나의 ''a'' 값이 아닌 충분히 많은 개수의 ''a'' 값에 대해 합동식 (2)가 성립하는지를 확인한다.

결론적으로, 적절한 ''r''과 충분히 많은 ''a'' 값들에 대해 합동식 (2)를 검증함으로써, AKS 알고리즘은 다항 시간 내에 주어진 정수 ''n''이 소수인지 합성수인지를 결정론적으로 판별할 수 있다.^[1] 이는 페르마 테스트가 카마이클 수와 같은 특정 합성수를 소수로 잘못 판정하는 문제를 해결한 개선된 방법으로 볼 수 있다.

4. 알고리즘

AKS 알고리즘의 개요는 다음과 같다.^[1]

입력으로 1보다 큰 정수 ''n''을 받는다.

# ''n''이 완전 제곱수인지 확인한다: 만약 $n=a^b$인 정수 ''a'' > 1 와 ''b'' > 1 가 존재하면, ''합성수''를 출력하고 종료한다. 이는 거듭제곱수 판정으로, 제5단계 판정법이 거듭제곱수에는 제대로 작동하지 않기 때문에 필요하다.

# $o\_\{r\}(n)\; >\; (\backslash log\_\{2\}\; n)^\{2\}$ (또는 일부 변형에서는 $4(\backslash log\; n)^2$)을 만족하는 가장 작은 ''r''을 찾는다. 여기서 $o\_\{r\}(n)$은 ''r''을 법으로 한 ''n''의 곱셈 위수, 즉 $n^\{k\}\; \backslash equiv\; 1\; \backslash pmod\{r\}$을 만족하는 가장 작은 양의 정수 ''k''이다. $\backslash log\_2$는 이진 로그 함수이다. 이러한 ''r''은 $r\; \backslash leq\; \backslash lceil\; 16(\backslash log\; n)^5\; \backslash rceil$ 범위 안에 존재함이 증명되어 있다. 만약 ''r''과 ''n''이 서로소가 아니면(즉, 최대공약수가 1보다 크면), ''n''의 비자명한 약수를 찾은 것이므로 ''합성수''를 출력하고 종료한다. 이는 제5단계가 올바르게 동작하기 위해 $n$이 $(\backslash mathbb\{Z\}/r\backslash mathbb\{Z\})^\backslash times$의 원이어야 하기 때문이다.

# 모든 2 ≤ ''a'' ≤ min(''r'', ''n''−1)에 대해 ''a''가 ''n''을 나누는지 확인한다 (또는, 어떤 ''a'' ≤ ''r''에 대해 인지 확인한다. 여기서 $(a,n)$는 ''a''와 ''n''의 최대공약수이다). 만약 이러한 ''a''가 존재하면, ''합성수''를 출력하고 종료한다. 이는 최대 ''r''까지의 시험 나눗셈과 동일하며 효율적으로 수행될 수 있다.

# 만약 ''n'' ≤ ''r''이면 ''소수''를 출력하고 종료한다. 이 경우는 제3단계에서 ''n''이 ''n''-1까지의 모든 수와 서로소임을 확인한 셈이므로 ''n''은 소수이다. 이 단계는 ''n''이 매우 작은 경우(예: 400 이하)에 해당될 수 있으며, 특정 임계값(예: 5690034)보다 큰 ''n''에 대해서는 생략될 수 있다.

# 1부터 $\backslash lfloor\; \backslash sqrt\{\backslash varphi(r)\}\backslash log\_2(n)\; \backslash rfloor$ (또는 $[2\backslash sqrt\{\backslash phi(r)\}\; \backslash log\; n]$)까지의 모든 정수 ''a''에 대해 다음 합동식이 성립하는지 검사한다. 여기서 $\backslash varphi(r)$은 오일러 피 함수이고, $[x]$는 가우스 기호이다.

#: $(X+a)^\{n\}\; \backslash equiv\; X^\{n\}+a\; \backslash pmod\{X^\{r\}-1,\; n\}$

#: 만약 이 합동식이 성립하지 않는 ''a''가 하나라도 존재하면, ''합성수''를 출력하고 종료한다. 이 합동식 검사는 다항식 환 $(\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]/(X^r\; -1)$에서 이루어지며, 계산 복잡도는 ''r''의 크기에 의존한다. 알고리즘의 핵심 연산이며, 대부분의 시간이 이 단계에서 소요된다.

# 위의 모든 단계를 통과하면, ''소수''를 출력하고 종료한다. 제5단계에서 충분히 많은 ''a''에 대해 합동식이 성립한다면 ''n''은 반드시 소수이거나 소수의 거듭제곱인데, 제1단계에서 거듭제곱인 경우는 이미 걸러졌으므로 ''n''은 소수이다.

AKS 소수 판별법은 다음 정리에 기반한다: 정수 $n\backslash ge\; 2$와 $n$과 서로소인 정수 $a$가 주어졌을 때, $n$이 소수일 필요충분조건은 다항식 환 $(\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]$에서 다음 합동 관계가 성립하는 것이다.^[1]

:$(X\; +\; a)^\{n\}\; \backslash equiv\; X^\{n\}\; +\; a\; \backslash pmod\{n\}$

이 정리는 페르마의 소정리를 다항식으로 일반화한 것이다. ''n''이 소수일 때 이 관계가 성립함은 이항 정리와, 모든

:$(X\; +\; a)^\{n\}\; \backslash equiv\; (X^\{n\}\; +\; a)\; \backslash pmod\{X^\{r\}-1,\; n\}$

알고리즘의 유효성 증명은 위의 조건을 만족하는 적절한 ''r''과 충분히 많은 ''a'' 값들에 대해 합동식이 성립하면 ''n''이 반드시 소수임을 보이는 데 중점을 둔다.^[1] 알고리즘 개선 연구는 주로 ''r''의 크기를 줄이고 제5단계의 핵심 연산을 더 빠르게 만드는 데 집중되어 왔다.^[5]

5. 알고리즘 해설

AKS 소수 판별법은 주어진 정수 ''n''이 소수인지 합성수인지를 결정하는 알고리즘이다. 이 알고리즘은 페르마의 소정리를 다항식으로 일반화한 다음 정리에 기반한다.

정수 $n\; \backslash ge\; 2$와 $n$과 서로소인 정수 $a$가 주어졌을 때, 다항식 환 $(\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]$ 내에서 다음 합동 관계

$(X\; +\; a)^\{n\}\; \backslash equiv\; X^\{n\}\; +\; a\; \backslash pmod\{n\}$

가 성립하는 경우에만 $n$은 소수이다.^[1] 여기서 $X$는 다항식 환을 생성하는 미지수를 나타낸다.

이 정리는 이항 정리와 소수 $n$에 대해

AKS 알고리즘은 이 합동 관계를 직접 확인하는 대신, 적절한 정수 $r$을 찾아 몫환 $(\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]/(X^r\; -1)$에서 평가함으로써 계산 복잡도를 다항 시간으로 줄인다. 즉, 다음 합동 관계를 확인한다.^[1]

$(X\; +\; a)^\{n\}\; \backslash equiv\; (X^\{n\}\; +\; a)\; \backslash pmod\{X^\{r\}-1,\; n\}$

이는 어떤 다항식 $f,\; g$에 대해 $(X\; +\; a)^n\; -\; (X^n\; +\; a)\; =\; (X^r\; -\; 1)g\; +\; nf$ 와 동치이다. 모든 소수 $n$은 이 관계를 만족한다 (첫 번째 합동식이 성립하므로 $g=0$으로 두면 된다). AKS 알고리즘은 이 합동 관계가 충분히 많은 $a$ 값에 대해 성립하는지 확인하여 $n$의 소수성을 판별한다. 알고리즘의 정확성 증명은 이러한 $r$과 $a$ 값 집합을 찾을 수 있으며, 만약 합동 관계가 모두 성립한다면 $n$은 소수의 거듭제곱이라는 것을 보인다.^[1]

알고리즘의 단계는 다음과 같다.^[1]

'''입력''': 정수 $n\; >\; 1$

1. 거듭제곱수 판별: $n\; =\; a^b$ 인 정수 $a\; >\; 1$ 와 $b\; >\; 1$ 가 존재하는지 확인한다. 만약 존재하면 "합성수"를 출력하고 종료한다. (거듭제곱수는 소수가 아니므로 미리 제외한다.)

2. r 찾기: $o\_r(n)\; >\; (\backslash log\_2\; n)^2$ 를 만족하는 가장 작은 정수 $r$을 찾는다. 여기서 $o\_r(n)$은 $n$의 모듈러 $r$에 대한 곱셈 위수, 즉 $n^k\; \backslash equiv\; 1\; \backslash pmod\{r\}$을 만족하는 가장 작은 양의 정수 $k$이다. 이러한 $r$은 $r\; \backslash leq\; \backslash lceil\; 16(\backslash log\_2\; n)^5\; \backslash rceil$ 범위 안에 존재함이 알려져 있다.

3. 최대공약수 확인: 모든 $2\; \backslash le\; a\; \backslash le\; \backslash min(r,\; n-1)$ 에 대해 $\backslash gcd(a,\; n)$을 계산한다. 만약 인 $a$가 존재하면(즉, $a$가 $n$의 비자명한 약수이면) "합성수"를 출력하고 종료한다. (일부 버전에서는 $r$을 찾는 과정에서 $\backslash gcd(n,\; r)\; \backslash neq\; 1$ 이면 합성수로 판정하기도 한다.)

4. 작은 수 판별: 만약 $n\; \backslash le\; r$ 이면 "소수"를 출력하고 종료한다. 이 경우, 3단계에서 $n$보다 작은 모든 수 $a$에 대해 $\backslash gcd(a,\; n)=1$ 임을 확인했으므로 $n$은 소수이다. (n > 5690034 이면 이 단계는 거의 발생하지 않아 무시될 수 있다.)

5. 다항식 합동식 확인: $a\; =\; 1$ 부터 $\backslash lfloor\; \backslash sqrt\{\backslash phi(r)\}\backslash log\_2(n)\; \backslash rfloor$ 까지의 모든 정수 $a$에 대해 다음 합동식이 성립하는지 확인한다. 여기서 $\backslash phi$는 오일러 피 함수이고, $\backslash lfloor\; \backslash cdot\; \backslash rfloor$는 바닥 함수이다.

$(X+a)^\{n\}\; \backslash equiv\; X^\{n\}+a\; \backslash pmod\{X^\{r\}-1,\; n\}$

만약 이 합동식을 만족하지 않는 $a$가 하나라도 존재하면, "합성수"를 출력하고 종료한다. 이 단계는 알고리즘의 핵심이며, 대부분의 계산 시간을 차지한다. 계산은 유한 환 $R\; =\; (\backslash mathbb\; Z/n\backslash mathbb\; Z)[X]/(X^r\; -1)$ 에서 수행된다.

6. 소수 판별: 5단계의 모든 $a$ 값에 대해 합동식이 성립하면, "소수"를 출력하고 종료한다.

알고리즘의 정확성은 각 단계의 정당성에 기반한다. 1, 3, 4단계는 $n$의 약수 존재 여부를 직접 확인하므로 자명하게 정확하다. 5단계에서 합동식이 성립하지 않으면 $n$이 합성수라는 것 또한 첫 번째 합동식의 성질로부터 유도된다. 증명의 가장 중요한 부분은 6단계, 즉 5단계의 모든 검사를 통과하면 $n$이 실제로 소수임을 보이는 것이다. 이는 5단계에서 검사하는 다항식들로 생성되는 $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})[x]/(X^r-1)$ 내 곱셈군의 크기에 대한 상한과 하한을 비교하여, 만약 $n$이 소수가 아니면서 1단계에서 걸러지지 않았다면(즉, 소수의 거듭제곱이 아니라면) 모순이 발생함을 보이는 방식으로 증명된다.^[1]

=== 예시: n = 31 ===

$n=31$이 소수인지 판별해보자.

1. $31\; =\; a^b$ 를 만족하는 정수 $a>1,\; b>1$는 없다. ($\backslash sqrt\{31\}\; \backslash approx\; 5.5$, $\backslash sqrt[3]\{31\}\; \backslash approx\; 3.1$, $\backslash sqrt[4]\{31\}\; \backslash approx\; 2.3$, )

2. $o\_r(31)\; >\; (\backslash log\_2\; 31)^2\; \backslash approx\; (4.95)^2\; \backslash approx\; 24.5$ 인 최소의 $r$을 찾는다.

• r=1: 위수 정의 안됨.
• r=2: $31\; \backslash equiv\; 1\; \backslash pmod\{2\}$, $o\_2(31)=1$.
• ...
• r=29: 29는 소수. $31\; \backslash equiv\; 2\; \backslash pmod\{29\}$. $31^k\; \backslash equiv\; 1\; \backslash pmod\{29\}$ 인 최소 k를 찾는다. 페르마의 소정리에 의해 $k$는 $\backslash phi(29)=28$의 약수이다. $31^1\; \backslash equiv\; 2$, $31^2\; \backslash equiv\; 4$, $31^4\; \backslash equiv\; 16$, $31^7\; \backslash equiv\; 2^7\; =\; 128\; \backslash equiv\; 12$, $31^\{14\}\; \backslash equiv\; 12^2\; =\; 144\; \backslash equiv\; -1\; \backslash pmod\{29\}$. 따라서 위수는 28이다. $o\_\{29\}(31)\; =\; 28\; >\; 24.5$ 이므로 $r=29$이다.

6. 시간 복잡도

AKS 소수 판별법의 시간 복잡도는 알고리즘이 처음 발표된 이후 여러 개선을 거쳐왔다. 2002년 아그라왈, 카얄, 삭세나가 발표한 원 논문 ''PRIMES is in P''에서는 알고리즘의 시간 복잡도를 $\backslash tilde\{O\}(\backslash log(n)^\{12\})$로 증명했다.^[1] 이는 입력값 ''n''의 자릿수에 대해 다항 시간 복잡도이지만, 실제 적용에는 다소 느린 속도였다. ($\backslash tilde\{O\}$ 표기는 점근 표기법의 하나로, 로그 다항식 인자를 포함한다.)

논문 발표 이후 헨드릭 렌스트라, 칼 포머란스, 페드로 베리즈베이티아(Pedro Berrizbeitia), 청치카이(Qizhi Cheng), 대니얼 번스타인 등 여러 수학자들의 후속 연구를 통해 알고리즘은 꾸준히 개선되었다. 이러한 개선은 주로 알고리즘의 핵심 매개변수 ''r''의 상한을 더 효율적으로 추정하고, 원분 다항식 및 유한체 이론 등을 활용하여 이루어졌다.

이러한 연구 결과들을 반영하여 업데이트된 논문에서는 시간 복잡도 상한이 $\backslash tilde\{O\}(\backslash log(n)^\{10.5\})$로 개선되었고, 이후 체 이론의 결과를 추가로 적용하여 현재는 $\backslash tilde\{O\}(\backslash log(n)^\{7.5\})$임이 엄밀하게 증명되었다.

2005년 포머란스와 렌스트라는 $\backslash tilde\{O\}(\backslash log(n)^\{6\})$ 연산으로 실행되는 변형 알고리즘을 시연했으며,^[3][4] 이것이 AKS 알고리즘의 실제적인 시간 복잡도일 것으로 널리 추정된다.

더 나아가, 아직 증명되지 않은 특정 수학적 가설들이 참이라면 시간 복잡도는 더욱 개선될 여지가 있다. 예를 들어, 아르틴 추측이나 소피 제르맹 소수의 밀도에 관한 추측이 참이라면, 시간 복잡도는 $\backslash tilde\{O\}(\backslash log(n)^6)$ 또는 그 이하로 줄어들 수 있다. 아그라왈, 카얄, 삭세나는 Agrawal의 추측이 참일 경우 $\backslash tilde\{O\}(\backslash log(n)^3)$ 복잡도를 갖는 변형을 제안하기도 했으나, 이 추측은 참이 아닐 가능성이 높다고 여겨진다.

6. 1. 각 단계별 시간 복잡도

각 단계의 계산 시간을 분석하면 다음과 같다.

# '''1단계 (완전 거듭제곱수 판별):''' p진 뉴턴 방법을 사용하여 각 자연수 ''b''에 대해 $\backslash sqrt[b]\{n\}$을 $\backslash tilde\{O\}(\backslash log(n)^2)$ 시간에 계산할 수 있다. ''n'' = ''a''^''b'' 형태에서 ''b''의 상한은 $\backslash log\_2\; n$이므로, 이 단계는 총 $\backslash tilde\{O\}(\backslash log(n)^3)$ 시간에 완료된다.

# '''2단계 (r 찾기):''' 알고리즘은 ''r'' ≤ $\backslash lceil\; 16\backslash log(n)^5\backslash rceil$인 ''r''을 찾는다. 이 과정은 $\backslash tilde\{O\}(\backslash log(n)^7)$ 시간에 수행될 수 있다.

# '''3단계 (최대공약수 확인):''' 유클리드 호제법을 사용하면 하나의 최대공약수를 $\backslash tilde\{O\}(\backslash log(n))$ 시간에 계산할 수 있다. 이를 최대 ''r''번 (즉, $O(\backslash log(n)^5)$번) 반복하므로, 이 단계는 $\backslash tilde\{O\}(\backslash log(n)^6)$ 시간이 걸린다.

# '''4단계 (작은 수에 대한 소수 판별):''' ''n''이 ''r''보다 작거나 같은지 단순히 비교만 하므로 $O(\backslash log\; n)$ 시간이 걸린다.

# '''5단계 (다항식 합동식 확인):''' $\backslash pmod\{X^r-1,\; n\}$ 연산에서 다항식의 차수는 최대 ''r''-1이고 계수는 최대 ''n''-1이다. 고속 푸리에 변환을 이용하면 다항식의 거듭제곱을 $\backslash tilde\{O\}(r\; \backslash log(n)^2)$ 시간에 계산할 수 있다. 이 확인 과정을 $\backslash sqrt\{\backslash phi(r)\}\; \backslash log\; n$회 반복해야 하므로, 총 시간 복잡도는 $\backslash tilde\{O\}(r\backslash sqrt\{\backslash phi(r)\}\; \backslash log(n)^3)$이다. ''r''의 상한을 대입하면 $\backslash tilde\{O\}(\backslash log(n)^\{10.5\})$가 된다.

# '''6단계 (소수 판별):''' 이전 단계들의 결과에 따라 ''n''이 소수인지 합성수인지를 결정하는 단계로, 상수 시간이 소요된다.

따라서, 기본적인 대수학 지식만 사용했을 때 AKS 알고리즘의 전체 시간 복잡도는 가장 시간이 많이 소요되는 5단계에 의해 $\backslash tilde\{O\}(\backslash log(n)^\{10.5\})$로 결정된다.

알고리즘의 전체 시간 복잡도는 ''r''의 크기에 크게 의존한다. 만약 ''r''의 상한을 더 줄일 수 있다면 전체 시간 복잡도를 개선할 수 있다.

• 체 이론(Sieve theory)의 결과를 이용하면 ''r'' = $O(\backslash log(n)^3)$임을 보일 수 있으며, 이를 통해 전체 시간 복잡도는 $\backslash tilde\{O\}(\backslash log(n)^\{7.5\})$로 개선된다.

• 아르틴 추측이 참이라면, ''r'' = $O(\backslash log(n)^2)$이다.
• 소피 제르맹 소수의 밀도에 관한 추측이 참이라면, ''r'' = $\backslash tilde\{O\}(\backslash log(n)^2)$이다.

7. 역사

AKS 소수 판별법은 2002년 8월 6일, 인도 칸푸르 공과대학교의 마닌드라 아그라왈(Manindra Agrawal), 니라지 카얄(Neeraj Kayal), 니틴 삭세나(Nitin Saxena)가 발표한 논문 "PRIMES is in P"를 통해 세상에 알려졌다.^[1][2] 이 알고리즘은 역사상 처음으로 '일반적'(general), '다항 시간(polynomial time)', '결정적(deterministic)', '무조건적'(unconditional)이라는 네 가지 중요한 속성을 동시에 만족시킨 소수 판별법으로 평가받는다. 이전의 알고리즘들은 오랜 시간에 걸쳐 개발되었지만, 이 네 가지 조건을 모두 충족시키지는 못했다.

• 일반성: AKS 알고리즘은 주어진 어떤 수에 대해서도 소수인지 판별할 수 있다. 이는 특정 종류의 수에만 적용 가능한 루카스-레머 소수 판별법(Lucas–Lehmer test, 메르센 소수 대상)이나 페핀의 검사(Pépin's test, 페르마 수 대상) 등과 차별화되는 점이다.
• 다항 시간: 알고리즘 실행 시간이 입력된 숫자의 자릿수에 대한 다항식으로 표현될 수 있다. 타원 곡선 소수 증명(ECPP)이나 애들먼-포머란스-루멜리 소수 판별법(APR) 같은 결정적 알고리즘도 존재하지만, 모든 입력에 대해 다항 시간 복잡도를 가지는지는 증명되지 않았다.
• 결정성: AKS 알고리즘은 주어진 수가 소수인지 합성수인지를 확률적인 요소 없이 결정적으로 판별한다. 이는 밀러-라빈 소수 판별법(Miller–Rabin)이나 베일리-PSW 소수 판별법(Baillie–PSW)과 같은 확률적 알고리즘과 구별된다. 확률적 알고리즘들은 빠른 시간 안에 결과를 내지만, 오류 가능성을 완전히 배제할 수는 없다.
• 무조건성: 알고리즘의 정확성이 아직 증명되지 않은 다른 수학적 가설에 의존하지 않는다. 예를 들어, 밀러 검사는 결정적이고 다항 시간 안에 실행되지만, 그 정확성은 일반화된 리만 가설이 참이라는 가정 하에서만 보장된다.

8. 수상

(작성할 내용 없음 - 원본 소스에 '수상' 관련 정보가 없습니다.)

9. 개선 및 변형

AKS 알고리즘이 발표된 이후, 여러 연구자에 의해 계산 속도를 높이기 위한 다양한 변형과 개선이 이루어졌다. 초기 논문에서 제시된 알고리즘의 점근적 시간 복잡도는 $\backslash tilde\{O\}(\backslash log(n)^\{12\})$였으나, 이는 다소 느슨한 상한이었다. 만약 소피 제르맹 소수 분포에 대한 널리 받아들여지는 추측이 사실이라면, 시간 복잡도는 $\backslash tilde\{O\}(\backslash log(n)^6)$으로 개선될 수 있었다.

발견 후 몇 달 동안 헨드릭 렌스트라(2002), 칼 포머란스(2002), 페드로 베리즈베이티아(Pedro Berrizbeitia, 2002), 쳉치샹(Qi Cheng, 2003), 대니얼 번스타인(2003a/b), 렌스트라와 포머란스(2003) 등이 새로운 변형을 발표하며 계산 속도를 크게 향상시켰다. 이러한 다양한 변형들의 등장으로, 크랜들과 파파도풀로스(Crandall and Papadopoulos)는 2003년 논문에서 이들을 묶어 "AKS-class" 알고리즘이라고 지칭하기도 했다.

이러한 연구 결과들을 반영하여 "PRIMES is in P" 논문은 AKS 알고리즘과 그 증명 방식을 새롭게 업데이트했다. 기본적인 아이디어는 유지되었지만, 알고리즘의 핵심 단계 중 하나인 ''r'' 값을 선택하는 방식이 개선되었고, 증명 과정은 원분 다항식과 유한체 이론을 중심으로 더욱 체계적으로 구성되었다. 이 업데이트를 통해 시간 복잡도 상한은 $\backslash tilde\{O\}(\backslash log(n)^\{10.5\})$로 개선되었고, 이후 체 이론의 결과를 추가로 활용하여 $\backslash tilde\{O\}(\backslash log(n)^\{7.5\})$까지 줄어들었다.

2005년에는 포머란스와 렌스트라가 $\backslash tilde\{O\}(\backslash log(n)^\{6\})$의 연산만으로 실행되는 AKS 변형을 발표했다.^[3] 이는 다시 한번 논문 업데이트로 이어졌다.^[4] 한편, 아그라왈, 카얄, 삭세나(Agrawal, Kayal, Saxena)는 Agrawal의 추측이 참일 경우 $\backslash tilde\{O\}(\backslash log(n)^\{3\})$ 복잡도를 갖는 변형을 제안했지만, 포머란스와 렌스트라는 이 추측이 아마도 거짓일 것이라는 휴리스틱한 논증을 제시했다.

AKS 알고리즘의 전체 실행 시간은 주로 알고리즘의 5단계, 즉 조건을 만족하는 적절한 ''r'' 값을 찾는 과정에 의해 결정된다. 따라서 ''r'' 값의 상한을 줄이는 것이 시간 복잡도를 개선하는 핵심이다.

• 체 이론을 이용하면 ''r''이 $O(\backslash log(n)^3)$보다 작다는 것을 보일 수 있으며, 이를 통해 실제 알고리즘의 시간 복잡도는 $\backslash tilde\{O\}(\backslash log(n)^\{7.5\})$임을 알 수 있다.

• 아르틴 추측을 가정하면 $r\; =\; O(\backslash log(n)^2)$이다.
• 소피 제르맹 소수의 밀도에 관한 추측이 옳다면 $r\; =\; \backslash tilde\{O\}(\backslash log(n)^2)$이다.

10. 미해결 문제 및 추측

AKS 알고리즘의 시간 복잡도를 현재 알려진 $\backslash tilde\{O\}(\backslash log(n)^\{6\})$보다 더 개선할 수 있는지 여부는 아직 해결되지 않은 문제이다.^[3][4] 알고리즘 실행 시간의 주요 부분은 5단계에서 결정되는 $r$의 크기에 따라 결정되는데, 이 $r$ 값을 더 작게 한정할 수 있다면 시간 복잡도를 개선할 수 있다.

몇 가지 증명되지 않은 수론의 가설(추측)들이 AKS 알고리즘의 시간 복잡도와 관련되어 있다. 만약 이 가설들이 참으로 증명된다면, $r$의 상한을 낮추어 알고리즘의 효율성을 높일 수 있다.

• 아그라왈의 추측(Agrawal's conjecture): 아그라왈, 카얄, 삭세나는 이 추측이 참일 경우 알고리즘이 $\backslash tilde\{O\}(\backslash log(n)^\{3\})$ 시간에 실행될 수 있는 변형을 제안했다. 그러나 포머란스와 렌스트라는 이 추측이 아마도 거짓일 것이라는 휴리스틱한 논증을 제시했다.^[4]
• 소피 제르맹 소수 밀도 추측: 이 추측이 참이라면, $r$은 $\backslash tilde\{O\}(\backslash log(n)^2)$로 추정된다.
• 아르틴 추측: 이 추측이 참이라면 $r$은 $O(\backslash log(n)^2)$로 추정된다.

참조

_[1] 논문 PRIMES is in P http://www.cse.iitk.[...]
_[2] 논문 It is easy to determine whether a given integer is prime https://www.ams.org/[...]
_[3] 간행물 Primality testing with Gaussian periods http://www.math.dart[...] 2005-07-20
_[4] 간행물 Primality testing with Gaussian periods http://www.math.dart[...] 2011-04-12
_[5] 간행물 Proving Primality After Agrawal-Kayal-Saxena https://cr.yp.to/pap[...] 2003-01-25
_[6] 문서 See AKS Talk page for a discussion on why 'Example 2: n is not Prime past Step 4' is missing.
_[7] 저널 PRIMES is in P http://www.cse.iitk.[...]