AKS 원시성 검정

The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P".^[1] 알고리즘은 일반화된 리만 가설과 같은 수학적인 추측에 의존하지 않고, 주어진 숫자가 다항식 시간에서 프라임인지 복합인지를 확실히 판단할 수 있는 최초의 알고리즘이었다. 분석 분야에 의존하지 않은 증거도 눈에 띈다.^[2] 2006년에 저자들은 괴델 상과 풀커슨 상을 모두 받았다.

중요도

AKS는 일반적, 다항식 시간, 결정론적, 무조건적으로 정확한 최초의 원시성-프로빙 알고리즘이다. 이전의 알고리즘은 수세기 동안 개발되어 기껏해야 이 특성들 중 세 가지를 달성했지만, 네 가지를 모두 달성하지는 못했다.

AKS 알고리즘은 주어진 일반 숫자의 원시성을 검증하는 데 사용할 수 있다. 많은 빠른 원시성 테스트는 특정 성질을 가진 숫자에 대해서만 효과가 있는 것으로 알려져 있다. 예를 들어, 루카스-레머 테스트는 메르센 수에만 효과가 있고, 페핀의 테스트는 페르마 수에만 적용할 수 있다.
알고리즘의 최대 실행 시간은 목표 번호의 자릿수에 대한 다항식으로 제한될 수 있다. ECPP와 APR은 결정적으로 특정 숫자가 prime이지만 모든 입력에 대해 다항식 시간 한계가 있는 것으로 알려져 있지 않다는 것을 증명하거나 반증한다.
알고리즘은 목표 번호가 프라임인지 복합인지 결정적으로 구별할 수 있도록 보장된다. Miller-Rabin 및 Baillie-와 같은 랜덤화 테스트PSW는 다항식 시간 내에 소수에게 소수성을 테스트할 수 있지만 확률론적 결과만 생성하는 것으로 알려져 있다.
AKS의 정확성은 입증되지 않은 어떤 종속기업 가설을 조건으로 하는 것이 아니다. 이와는 대조적으로 밀러의 밀러-라빈 테스트 버전은 완전히 결정론적이며 모든 입력에 걸쳐 다항식으로 실행되지만, 그 정확성은 아직 증명되지 않은 일반화된 리만 가설의 진실에 달려 있다.

알고리즘이 이론적으로 대단히 중요한 반면, 실제로는 사용되지 않아 은하 알고리즘이 된다. 64비트 입력의 경우, Baillie-PSW 원시성 테스트는 결정론적이며 많은 수의 진도를 더 빨리 실행한다. 더 큰 입력의 경우, (또한 무조건적으로 올바른) ECPP와 APR 테스트의 성능이 AKS보다 훨씬 우수하다. 또한 ECPP는 AKS 알고리즘으로는 불가능한 독립적이고 신속한 결과 검증이 가능한 원시성 인증서를 출력할 수 있다.

개념

AKS 원시성 테스트는 다음과 같은 정리에 $n$ 한다: 다항식 일치 관계를 갖는 경우에만 정수 $n\geq 2$ $n\geq 2$ $n\geq 2$ ${\$ $displaystyle$ $n$ $n$ 과 $n\geq 2$ $a$ $정수$ a ${\displaystyle$ a $}$ 을(를 $)$ n ${\displaystyle$ n}에 $n$ 할당한다.

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

(1)

다항식 링 $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ [ $\mathbb {Z} _{n}[X]$ ] $\mathbb {Z} _{n}[X]$ {\ $displaystyle \mathb {Z} _{n}[X]}$ 내에 holds. $X$ $X$ 은 이 다항식 링을 생성하는 불확정성을 가리킨다는 $X$ 점에 유의하십시오 $\mathbb {Z} _{n}[X]$ ^[1]

이 정리는 페르마의 작은 정리의 다항식들에 대한 일반화다. 한 방향으로 이항 계수의 다음과 같은 특성과 함께 이항 정리를 사용하여 쉽게 증명할 수 있다.

{n \choose k}\equiv 0{\pmod {n}}

{n \choose k}\equiv 0{\pmod {n}}

)

{n \choose k}\equiv 0{\pmod {n}}

0

{n \choose k}\equiv 0{\pmod {n}}

(

{n \choose k}\equiv 0{\pmod {n}}

{n \choose k}\equiv 0{\pmod {n}}

)

{\

n

\select k}\equiv

0

{\pmod{n}}

n

{\

displaystyle n}

이

0<k<n

n

(가

)

prime이면

0<k<n

0

{n \choose k}\equiv 0{\pmod {n}}

0<k<n

<

0<k<n

<

{\displaystystyle 0>

0<

k<n}.

관계 (1)이 그 자체로 원시성 시험을 구성하지만, 그것을 검증하는 데는 지수적인 시간이 걸린다: 흉력 접근은 $(X+a)^{n}$ + a $(X+a)^{n}$ ) $(X+a)^{n}$ ${\$ $}$ 다항식의 $(X+a)^{n}$ 확장과 결과 $n+1$ + $n+1$ $n+1$ 계수의 $n+1$ 감소 ${\pmod {n}}$ n ${\pmod {n}}$ )를 $필요로 한다$ ..

합치는 다항 링 $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ [ X $\mathbb {Z} _{n}[X]$ $\mathb {Z} _{n}[X]$ 에서 동일하다 $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ [ $\mathbb {Z} _{n}[X]$ $\mathbb {Z} _{n}[X]$ $\mathb {Z} _{n}[X]$ 의 지수 링에서 평가하면 관련된 다항 링의 정도에 대한 상한이 생성된다 $\mathbb {Z} _{n}[X]$ . AKS는 $\mathbb {Z} _{n}[X]/(X^{r}-1)$ [ $\mathbb {Z} _{n}[X]/(X^{r}-1)$ $\mathbb {Z} _{n}[X]/(X^{r}-1)$ / $\mathbb {Z} _{n}[X]/(X^{r}-1)$ ( $\mathbb {Z} _{n}[X]/(X^{r}-1)$ $\mathbb {Z} _{n}[X]/(X^{r}-1)$ - 1 $\mathbb {Z} _{n}[X]/(X^{r}-1)$ ) ${\displaystyle \mathb {Z} _{n}[X]/(X^{r}-1)$ 에서 동일성을 평가하여 계산 복잡성은 $r$ $r$ 의 크기에 따라 달라지게 한다 $r$ 명확성을 위해,^[1] 이를 조합으로 표현한다.

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

(2)

이는 다음과 같다.

(X+a)^{n}-(X^{n}+a)=(X^{r}-1)g+nf

(3)

일부 다항식 $f$ $f$ 및 $g$ $g$ 의 경우 $g$

모든 프리임이 이 관계를 만족한다는 점에 유의하십시오(3에서 $g=0$ $g=0$ = 0 $g=0$ 을 선택하면 $n$ $n$ prime을 $n$ 유지하는 (1)이 부여된다. $r$ $r$ 이 $r$ (가) $n$ $n$ 의 숫자에 대해 다항식인 경우 이 결합을 다항식으로 확인할 수 있다 $n$ AKS 알고리즘은 $a$ 가 $n$ $n$ 의 숫자에 대한 다항식인 $a$ 값의 $a$ 큰 집합에 대해 이 합치를 평가한다 $n$ AKS 알고리즘의 유효성을 증명하면 $r$ 의 속성을 가진 r {\ $displaystyle$ r}^[1] 및 {\ $displaystyle a}$ $a$ 집합을 $r$ 찾을 수 있으며, 합치가 유지될 $경우$ n ${\$ $displaystyle n}$ 은 $n$ prime의 힘이다.

기록 및 실행 시간

In the first version of the above-cited paper, the authors proved the asymptotic time complexity of the algorithm to be ${\tilde {O}}(\log(n)^{12})$ (using Õ from big O notation)—the twelfth power of the number of digits in n times a factor that is polylogarithmic in the number of digits. 그러나 이 상한은 다소 느슨했다. 만일 사실이라면 소피 제르맹 프라임의 분포에 대한 널리 알려진 추측으로 최악의 경우를 O ~ ( ${\tilde {O}}(\log(n)^{6})$ ( ${\tilde {O}}(\log(n)^{6})$ ) 6 $){\displaystyle {\tilde{O}(\$ log(n)^{ $6})$ 로 바로 줄일 수 있을 것이다 ${\tilde {O}}(\log(n)^{6})$

발견 후 몇 달 동안 새로운 변형이 나타났으며(Lenstra 2002, Pomerance 2002, Berrizbytia 2002, Chen 2003, Berstein 2003a/b, Lenstra, Pomerance 2003) 연산 속도가 크게 향상되었다. 많은 변종이 존재하기 때문에 크랜달과 파파도풀로스는 2003년 3월에 발표한 과학 논문 「AKS급 원시성 시험의 이행에 관하여」에서 알고리즘의 「AKS급」을 언급하고 있다.

이러한 변종들 중 일부와 다른 피드백에 대응하여, "PRIMES is in P" 논문은 AKS 알고리즘의 새로운 공식화 및 정확성 증명으로 업데이트되었다. (이 버전은 결국 수학 연보에 실렸다.) 기본적인 생각은 그대로인 반면, r은 새로운 방식으로 선택되었고, 정확성의 증명은 보다 조리 있게 정리되었다. 새로운 증거는 거의 유한한 분야에 대한 사이클로토믹 다항식의 행동에 전적으로 의존했다. 새로운 상한 시간 복잡성은 ${\tilde {O}}(\log(n)^{10.5})$ ~ ${\tilde {O}}(\log(n)^{10.5})$ ( ${\tilde {O}}(\log(n)^{10.5})$ ${\tilde {O}}(\log(n)^{10.5})$ ${\tilde {O}}(\log(n)^{10.5})$ ) ${\tilde {O}}(\log(n)^{10.5})$ 5 ${\tilde {O}}(\log(n)^{10.5})$ ) ${\displaystyle {\tilde{O}(\log(n)^{10.$ 5 ${\tilde {O}}(\log(n)^{10.5})$ 나중에 체 이론에서 ${\tilde {O}}(\log(n)^{7.5})$ ~ ${\tilde {O}}(\log(n)^{7.5})$ ( ${\tilde {O}}(\log(n)^{7.5})$ ${\tilde {O}}(\log(n)^{7.5})$ 7 ${\tilde {O}}(\log(n)^{7.5})$ $){\displaystyle$ {\tilde ${O}(log(n)^{7$ .5 ${\tilde {O}}(\log(n)^{7.5})$ 로 추가 결과를 사용하여 축소했다.

2005년에 포머런스와 렌스트라는 ${\tilde {O}}(\log(n)^{6})$ log ${\tilde {O}}(\log(n)^{6})$ ( ${\tilde {O}}(\log(n)^{6})$ ) 6 ${\tilde {O}}(\log(n)^{6})$ ) ${\displaystyle {\tilde{O}(\log(n)^{6})$ 운영으로 ${\tilde {O}}(\log(n)^{6})$ 실행되는 AKS의 변형을 시연하여 논문의 또 다른 업데이트 버전을 이끌어냈다.^[3]^[4] 아그라왈, 카얄, 색세나는 아그라왈의 추측이 사실이라면 ${\tilde {O}}(\log(n)^{3})$ ${\tilde {O}}(\log(n)^{3})$ ~ ${\tilde {O}}(\log(n)^{3})$ ( ${\tilde {O}}(\log(n)^{3})$ ${\tilde {O}}(\log(n)^{3})$ ( ${\tilde {O}}(\log(n)^{3})$ ) $){\displaystyle{\tilde{O}(\log(n)^{3})}}$ 에서 실행되는 변종을 제안했지만, 포메란스와 렌스트라의 휴리스틱 주장은 아마도 거짓일 것이라고 제안했다.

알고리즘

알고리즘은 다음과 같다.^[1]

입력 :

정수

n >

1

.

n이 완벽한 전력인지 점검한다: $n$ = $a$ 의^b 정수 $a$ > $1$ 과b > 1 $출력$ 복합체.
$ord r (n)$ > ( $log$ $n 2$ )과 같은 가장 작은 r을 찾는다 $. 2$ (r과 n이 동일하지 않을 경우, 이 r을 건너뛰십시오)
모든 2㎛ a min(r, n-1)에 대해 a가 n을 나누지 않는지 점검한다. if a가 2㎛ a min(r, n-1)일 경우 출력복합체.
n ≤ r이면 prime을 출력한다.
$a$ = $1$ ~ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ ( r $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ ) $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ ${\$ sqloor {\ $sqrt{\varpi (r)}}\log _{2}(n)\right\rfloor$ } do $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ .
(X+a)≠ⁿ Xⁿ+a (mod^r X - 1,n), 출력 복합체;
출력 프라임.

여기서 ord_r(n)는 n modulo r의 승수 순서, log는₂ 이항 로그, $\varphi (r)$ ( $\varphi (r)$ ) $\varphi(r)$ 는 오일러의 r의 총함수다 $\varphi (r)$ .

3단계는 1< (a,n) < n을 확인하여 모든 ≤ r로 표시한다. 이는 gcd를 사용하지 않고도 매우 효율적으로 할 수 있는 r까지의 시험분할에 해당한다고 볼 수 있다. 마찬가지로 4단계의 비교는 $displaystyle \left\lfloor{\sqrt{n}\$ right $\rfloor .}$ 까지의 모든 값을 확인한 후 시험 분할이 prime을 반환하도록 하는 것으로 대체할 수 있다.

일단 매우 작은 입력 범위를 벗어나면, 5단계는 소요 시간을 지배한다. (지수에서 다항식까지의) 복잡성의 본질적인 감소는 유한 링에서 모든 계산을 수행함으로써 달성된다.

R:={\bigl (}\bigl (}\mathb {Z} /(n){\bigr )}[X]{\Bigr )}{\bigl /}(X^{r}\!\!1){\Bigr.}

$n\cdot r$ $n\cdot r$ $n\cdot r$ $n\cdot r$ 요소로 $n\cdot r$ 구성된다. This ring contains only the $r$ monomials $\{X^{0},X^{1},\ldots ,X^{r-1}\}$ , and the coefficients are in $\mathbb {Z} /(n)=:\mathbb {Z} _{n}$ which has $n$ elements all of them codable within $\log _{2}(n)$ $\log _{2}(n)$ $\log _{2}(n)$ ( $\log _{2}(n)$ ) $\log _{2}(n)$ 비트 $\log _{2}(n)$ .

알고리즘에 대한 대부분의 후기 개선은 5단계에서 코어 작동을 더 빠르게 하는 r의 크기를 줄이는 것과 s의 크기를 줄이는데 집중되었다.^[5] 전형적으로 이러한 변화는 계산 복잡성을 변화시키지 않지만, 예를 들어 번스타인의 최종 버전은 200만 배 이상의 이론적 속도 증가를 가지고 있다.

타당성 증명 개요

알고리즘이 정확하려면 n을 식별하는 모든 단계가 정확해야 한다. 1단계, 3단계, 4단계는 n의 불능성에 대한 직접 시험에 기초하기 때문에 약간 정확하다. 또한 5단계는 정확하다: (2) n이 소수일 경우 n과 r에 대한 모든 조합 선택에 대해 참이기 때문에, 불평등은 n이 복합적이어야 함을 의미한다.

알고리즘의 어려운 경우는 5단계의 반복문이다. 만약 이것이 유한한 Ring R 내에 부조화를 초래한다면

u\not \equiv v\;{\bigl (}{\text{mod }}}}}(X^{r}\!\\\),n{\bigr )}}}}

이것은 와 같다

u\equiv v\;{\bigl (}{\text{mod }}(X^{r}\!\!-\!\!1){\bigr )}\quad \implies \quad u\not \equiv v\;({\text{mod }}n)

,

따라서 ${\text{mod }}(X^{r}\!\!-\!\!1)$ r - ${\text{mod }}(X^{r}\!\!-\!\!1)$ $){\displaystyle{\text{mod}}}}(X^{r}\\\!-\\!1$ )을 통해 r 단수까지 줄인 후 $u\not \equiv v\;({\text{mod }}n)$ $u\not \equiv v\;({\text{mod }}n)$ $u\not \equiv v\;({\text{mod }}n)$ ( $u\not \equiv v\;({\text{mod }}n)$ n $){\displaysty u\not \equivv\;({\text{\mod{}n$ )}n $)})})$ 만 ${\text{mod }}(X^{r}\!\!-\!\!1)$ 확인해야 한다 $u\not \equiv v\;({\text{mod }}n)$ .^[1]

예제 1: n = 31은 prime임

입력: 정수 n = 31 > 1

  n = a의^b 정수 a > 1과 b > 1인 경우 복합체를 출력한다.     [b=2, b <= log₂(n), b++, a=n^1/b; [ a가 정수인 경우 Return[Composite]] ]; a=n^1/2...n^1/4={5.568, 3.141, 2.360}

  O_r(n) > (log₂ n).² maxk=max(log₂ n)⌋;² maxr=max=max[3, ⌈(Log₂ n)⌉];⁵ (*maxr really need*) nextR=와 같은 가장 작은 r을 찾는다.참; [r=2, nextR&&&r < maxr, r++, nextR=false; [k=1, (!nextR) &&k k maxk, k+++, nextR=(Mod[n^k^k, r]=0)]; r--;(*루프가 1씩 증가함*) = r =

  일부 ≤ r에 대해 1 < gcd(a,n) > n이면 복합체를 출력한다.     [a=r, a > 1, a-, 만약 [(gCD=GCD[a,n])]이 1 &&gcd <n, Return[Composite]] ];; gcd={GCD(29,31)=1, GCD(2,31)=1, ..., GCD(2,31)=1.

  n ≤ r이면 prime을 출력한다.     [n ≤ r, Return[Prime]인 경우; (* 이 단계는 n > 5690034 *) 31 > 29인 경우 생략할 수 있다.

  a = 1 ~  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$  (  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ )  $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$   $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$   $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ ( $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ )  $⌋$  {\ $displaystyle \left\lfloor {\$ sqloor {\ $sqrt {\barphi (r)}\log _{$ 2}(n $)\$ }이 $\left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor$ (mod X^r - 1,n)인 경우ⁿ 복합 출력이 φ[x_x_x_x_:::=UlerPi[x];     PolyModulo[f_]:=폴리놈모드[PollynomialMod][f,x-1^r,x],n]; max=플로어[Log[2,n]loglog[r];     For[a=1,≤ max, a++, 만약 -LSB- PolyModulo[(x+a)n-PolynomialRemainder는 경우에는 xn+a, xr-1],)]≠0, Return[합성]하는 방법에 대한 해결;(x+a)31)a31 +31a30x +465a29x2 +4495a28x3 +31465a27x4 +169911a26x5 +736281a25x6 +2629575a24x7 +7888725a23x8 +20160075a22x9 +44352165a21x10 +84672315a20x11 +141120525a19x12 +206253075a18x13 +265182525a17x.14+300540195a16x15+265182525a14x17 +20625 +300540195a15x16.3075a13x18 +141120525a12x19 +84672315a11x20 +44352165a10x21 +20160075a9x22 +7888725a8x23 +2629575a7x24 +736281a6x25 +169911a5x26 +31465a4x27 +4495a3x28 +465a2x29 +31ax30 +x31 PolynomialRemainder[(x+a cm31일 x29-1])465a2 +a31 +(31a+31a30)x +(1+465a29)x2 +4495a28x3 +31465a27x4 +169911a26x5 +736281a25x6 +2629575a24x7 +7888725a23x8 +201.60075a22x9 +44352165a21x10+141120525a19x12 +206253075a18x13 +265182525a17x14 +30 +84672315a20x11.0540195a16x15 +300540195a15x16 +265182525a14x17 +206253075a13x18 +141120525a12x19 +84672315a11x20 +44352165a10x21 +20160075a9x22 +7888725a8x23 +2629575a7x24 +736281a6x25 +169911a5x26 +31465a4x27 +4495a3x28(A)PolynomialMod[PolynomialRemainder[(x+a cm31일 x29-1], 31 뻗는다)a31+x2(B)PolynomialRemainder[x31+a,x29-1])a+x2.         (A)-(B))a31+x2-(a+x2))a31-a max)⌊ 접속한다. $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$ ( $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$  )  $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$ ( $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$ )  $\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor$   ${\$ 2}( $31){\sqrt {\varphi (29)}}\barphi$  (29 $)}}}}}$  = 26 {1-1³¹=0(mod 31), 2-2³¹=0(md31), 3³¹=0(mod 31), ..., 26-226³¹=0(mod 31)

  출력 프라임. 31 반드시 프라임이어야 함

여기서 PolynomialMod는 다항식 모듈로 축소(예: PolynomialMod[x+2x²+3x³, 3] = x+2x²+0x³

^[6]

참조

^ ^a ^b ^c ^d ^e ^f Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.
^ Granville, Andrew (2005). "It is easy to determine whether a given integer is prime". Bull. Amer. Math. Soc. 42: 3–38. doi:10.1090/S0273-0979-04-01037-7.
^ H. W. Lenstra Jr.와 Carl Pomerance, "가우스 시기의 기본성 시험", 2005년 7월 20일 예비 버전.
^ H. W. Lenstra Jr.와 Carl Pomerance, 2011년 4월 12일 버전 "웨이백 기계에 보관된 2012-02-25 가우스 기간을 사용한 기본성 테스트".
^ 다니엘 J. 번스타인, 2003년 1월 25일판 "아그라왈-카얄-색세나 이후 프라임리티 입증"
^ '예 2: n은 Prime past step 4'가 누락된 이유에 대한 자세한 내용은 AKS Talk 페이지를 참조하십시오.

추가 읽기

Dietzfelbinger, Martin (2004). Primality testing in polynomial time. From randomized algorithms to PRIMES is in P. Lecture Notes in Computer Science. Vol. 3000. Berlin: Springer-Verlag. ISBN 3-540-40344-2. Zbl 1058.11070.

외부 링크

[AKS-1] ^ ^a ^b ^c ^d ^e ^f Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.

[2] Granville, Andrew (2005). "It is easy to determine whether a given integer is prime". Bull. Amer. Math. Soc. 42: 3–38. doi:10.1090/S0273-0979-04-01037-7.

[lenstra_pomerance_2005-3] H. W. Lenstra Jr.와 Carl Pomerance, "가우스 시기의 기본성 시험", 2005년 7월 20일 예비 버전.

[lenstra_pomerance_2011-4] H. W. Lenstra Jr.와 Carl Pomerance, 2011년 4월 12일 버전 "웨이백 기계에 보관된 2012-02-25 가우스 기간을 사용한 기본성 테스트".

[bernstein03-5] 다니엘 J. 번스타인, 2003년 1월 25일판 "아그라왈-카얄-색세나 이후 프라임리티 입증"

[6] '예 2: n은 Prime past step 4'가 누락된 이유에 대한 자세한 내용은 AKS Talk 페이지를 참조하십시오.

[1]

[2]

[3]

[4]

[5]

[6]

v t 수이론적 알고리즘
원시성 검정	AKS APR 바일리-PSW 타원곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로트의 정리 페핀스 이차적 프로베니우스 솔로베이-스트라센 밀러-라빈
프라임 생성	앳킨의 체 에라토스테네스의 체 순다람의 체 휠 인자화
정수 인자화	지속분수(CFRAC) 딕슨스 Lenstra 타원 곡선(ECM) 오일러즈 폴라드 호 p − 1 p + 1 2차 체(QS) 일반수 필드 체(GNFS) 특수수 필드 체(SNFS) 이성 체 페르마츠 샨크스의 사각형 재판분할 쇼르스
곱하기	고대 이집트인 긴 카라츠바 툼-쿡 sch나게-스트라센 총통의
유클리드 주 나누기	이진수 청킹 푸리에 골드슈미트 뉴턴-래프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드 캥거루 포흘리그-헬먼 지수 미적분학 기능장 체
최대공통점	이진수 유클리드 주 확장유클리드 르메르스
모듈형 제곱근	시폴라 포클링턴스 토넬리-상크스 베를레캄프 쿠네르스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈형 지수 몽고메리 환원 슈프
이탤릭체는 알고리즘이 특수형태의 숫자에 대한 것임을 나타낸다.

Search