소수판별법

수론에서, 소수판별법은 어떤 자연수 N이 소수인지 합성수인지를 판별하는 알고리즘들을 말한다.

간단한 방법들

직접 나누기

직접 나누기 (Trial Division)는 소수 판별법 중에서 가장 간단한 예시로, 어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한 번이라도 나누어 떨어지면 합성수, 아니면 소수라고 판정하는 방법이다. 보통 다른 소수 판별법을 하기에 앞서서 특정 범위까지 나눠 보는 방식으로 많이 사용되며, 이 방법을 이용하여 어떤 수를 소인수 분해 할 수도 있다. 이 방법은 간단하고 편리하지만 다른 소수 판별법 중에서 가장 비효율적인 방식에 속하며 여러 소인수 분해 방법들 중에서도 가장 비효율적인 방법에 속한다.

윌슨의 정리

윌슨의 정리 (Wilson's Theorem)를 이용한 방법은 소수에서만 성립하는 다음 성질을 이용한 것이다.

$(p-1)!\equiv -1{\pmod {p}}$

어떤 자연수 n이 소수인지 합성수인지를 판별하려면 위 공식의 p의 자리에 n을 대입해서 결과가 -1이 나오면 소수, 아니면 합성수라고 하면 된다. 이 방법은 직접 나누는 방법과 같이 간편하지만 p가 30 이상이 되면 그 팩토리얼을 계산하기 힘들어지기 때문에 거의 쓰이지 않는다.

확률론적 방법들

확률론적 방법을 이용해서 나온 결과가 합성수이면 어떤 자연수 N은 합성수이지만, 결과가 소수로 나왔다고 해서 반드시 소수가 되지는 않는다. 따라서 어떤 자연수 N을 대입했을 때 나온 결과가 소수이면 이 수는 확률적 소수가 된다.

페르마 소수판별법

페르마 소수판별법 (Fermat's Primality Test)은 페르마 소정리를 이용하는 것으로, a와 p가 서로소이고 a<p이며 p가 소수일 때는 반드시 성립하는 다음의 관계식을 이용한 것이다.

$a^{p-1}\equiv 1{\pmod {p}}$

만약 어떤 자연수 N을 이 식의 p 자리에 대입했을 때 성립하지 않으면 N은 합성수이다. 반대로, 어떤 자연수 N이 다음의 관계를 만족하면 이 수는 확률적 소수이며, 그렇다고 해서 이 수가 반드시 소수가 되지는 않는다.

솔로바이-스트라센 소수판별법

솔로바이-스트라센 소수판별법 (Solovay-Strassen Primality Test)은 레온하르트 오일러가 발견한 정리를 이용한다. 어떤 소수 p와 이 소수 p와 서로소인 정수 a에 대하여 다음 관계식이 성립한다.

$a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$

여기서 오른쪽 기호는 야코비 기호이다. 만약 어떤 정수 p와 이 정수에 서로소인 정수 a에 대하여 위의 관계식이 성립하지 않으면 p는 합성수이고, 아니면 p는 확률적 소수가 된다.

밀러-라빈 소수판별법

밀러-라빈 소수판별법 (Miller-Rabin Primality Test)은 다음과 같이 작동한다. 소수인지 확인하고 싶은 수를 N이라고 하고, N-1을 2^s·d (d는 홀수)꼴로 분해한다. 만약 어떤 양의 정수 a와 0 ≤ r ≤ s − 1인 어떤 r에 대하여

$a^{d}\equiv 1{\pmod {N}}$

또는

$a^{2^{r}\cdot d}\equiv -1{\pmod {N}}$

이라면 N은 확률적 소수이다. 만약 위 두 식이 모두 성립하지 않으면, N은 합성수이다.

일반적으로 밀러-라빈 소수판별법은 솔로바이-스트라센 소수판별법보다 강력하다. 즉, 밀러-라빈 소수판별법은 솔로바이-스트라센 소수판별법보다 더 효과적으로 합성수를 걸러낼 수 있다. 또한 일반화 리만 가설이 맞다면 $\lfloor 2(\ln N)^{2}\rfloor$개의 a로 이 소수판별법을 이용했을 때 결과가 모두 소수로 나오면 이 수는 실제로 소수가 된다.

뤼카 소수판별법 (확률적)

뤼카 소수판별법 (Lucas Probable Prime Test)는 수학자 에두아르 뤼카 (Édouard Lucas)의 이름을 따서 만들어진 소수판별법으로, 다음과 같이 작동한다.

어떤 수 n과 임의의 정수 P>0, Q, 그리고 $D=P^{2}-4Q\neq 0$에 대하여 우리는 다음과 같은 함수 $\delta (n)=n-\left({\frac {D}{n}}\right)$와 뤼카 수열

$U_{0}=0,U_{1}=1,U_{k}=PU_{k-1}-QU_{k-2}$

그리고

$V_{0}=2,V_{1}=P,V_{k}=PV_{k-1}-QV_{k-2}$

를 정의할 수 있다. 만약 n, P, Q, 그리고 D에 대하여

$U_{\delta (n)}\equiv 0{\pmod {n}}$

이라는 관계식이 성립하면, n은 확률적 소수이다. 만약 이 식이 성립하지 않으면 n은 합성수가 된다.

강한 뤼카 소수판별법 (확률적)

강한 뤼카 소수판별법 (Strong Lucas Probable Prime Test)은 뤼카 소수판별법을 개량하여 만든 소수판별법으로, 뤼카 소수판별법보다 더 강력하다.

만약 뤼카 수열 $U_{n}$과 $V_{n}$, 그리고 부등식 0 ≤ r < s를 만족하는 어떤 r에 대하여

$U_{d}\equiv 0{\pmod {n}}$

또는

$V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}$

이라면 n은 확률적 소수이다. 만약 이 두 식이 모두 성립하지 않으면 n은 합성수이다.

매우 강한 뤼카 소수판별법 (확률적)

매우 강한 뤼카 소수판별법 (Extra Strong Lucas Probable Prime Test)는 다음과 같이 작동한다. 만약 뤼카 수열 $U_{n}$과 $V_{n}$, 그리고 부등식 0 ≤ r < s를 만족하는 어떤 r에 대하여

(1) $U_{d}\equiv 0{\pmod {n}}$ 그리고 $V_{d}\equiv \pm 2{\pmod {n}}$

또는

(2) $V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}$

만약 (1)과 (2) 중 하나라도 성립하면 n은 확률적 소수가 되고, (1)과 (2)가 모두 성립하지 않으면 n은 합성수가 된다. 또한 이 소수판별법은 강한 뤼카 소수판별법보다 더 강력하다.

베일리-PSW 소수판별법

베일리-PSW 소수판별법 (Baillie-PSW Primality Test)은 로버트 베일리, 칼 포머런스, 존 셀프리지, 그리고 사무엘 웨그스태프의 이름을 따서 만든 소수판별법이다. 이 소수판별법은 a=2일 때의 밀러-라빈 소수판별법을 먼저 실행한 후, 강한 뤼카 소수판별법을 이용하여 한 번 더 소수판별법을 실행한 후 후속적으로 몇 가지 검사를 더 한다. 현재까지는 2⁶⁴ 미만의 수들에 대해 이 소수판별법을 이용했을 경우 실제의 결과와 한 번도 틀리지 않았기 때문에 아마도 결정론적 소수판별법이라고 추측되지만, 아직 증명이 되지는 않았다.

결정론적 소수판별법

결정론적 소수판별법들은 결과가 소수로 나오면 그 수는 무조건적으로 소수가 되고, 합성수라고 나오면 그 수는 무조건적으로 합성수인 알고리즘들이다.

뤼카-레머 소수판별법

뤼카-레머 소수판별법 (Lucas-Lehmer Primality Test)은 메르센 수에만 적용할 수 있는 소수판별법이다. 어떤 메르센 수 M_p = 2^p − 1에서 p가 홀수 소수일 때 (만약 p가 합성수이면 이 메르센 수는 1보다 큰 약수를 반드시 가지게 된다), 우리는 다음 수열을 정의할 수 있다.

$s_{0}=4,s_{i}=s_{i-1}^{2}-2$

만약 $s_{p-2}\equiv 0{\pmod {2^{p}-1}}$이라면 이 메르센 수는 소수가 되고, 아닌 경우에는 합성수가 된다.

뤼카-레머-리젤 소수판별법

뤼카-레머-리젤 소수판별법 (Lucas-Lehmer-Riesel Primality Test)은 N = k ⋅ 2ⁿ − 1 (k < 2ⁿ)형태의 수 N에 대하여 적용할 수 있는 소수판별법이다. 이 소수판별법은 뤼카-레머 소수판별법과 거의 똑같으며, 다만 k의 값에 따라 초깃값 (s₀)을 다르게 정한다. 아래는 k의 값에 대한 초깃값(s₀)들이다.

• k = 2이거나 k = 4일 때는 n의 값에 1 또는 2를 더하여 뤼카-레머 소수판별법을 적용한다.
• k = 1이고 n이 홀수이면 이 소수판별법은 뤼카-레머 소수판별법과 똑같아진다. 따라서 s₀=4이다. 만약 k = 1이고 n ≡ 3 (mod 4)이면 s₀=3으로 해도 된다.
• k = 3이고 n ≡ 0 또는 3 (mod 4)이라면 s₀=5778이다.
• k ≡ 1 또는 5 (mod 6)이고 $3\nmid N$이면 $s_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$이다.
• 위의 경우에 모두 속하지 않는 경우, 다음과 같이 s₀을 구하면 된다.
  • 1. 두 식 $\left({\frac {P-2}{N}}\right)=1$ 그리고 $\left({\frac {P+2}{N}}\right)=-1$을 만족시키는 자연수 P를 구한다. 만약 $3\nmid k$이면 P=4로 해도 된다. 여기서 각 등식의 왼쪽 항의 기호는 야코비 기호이며, 5, 8, 9, 11 중 어느 하나라도 P의 조건을 만족할 확률은 85% 정도이다.
  • 2. 위에서 구한 값 P와 Q=1을 이용하여 뤼카 수열 중 k번째 항인 $V_{k}$를 구한다. 이때, $s_{0}=V_{k}$가 된다.

위 과정에 따라서 초깃값을 정한 후 $s_{i}=s_{i-1}^{2}-2$를 이용하여 $s_{n-2}$의 값을 구한다. 만약 $s_{n-2}\equiv 0{\pmod {N}}$이면 N은 소수, 아니면 합성수이다.

프로트의 정리

프로트의 정리 (Proth's Theorem)는 어떤 프로트 수가 소수인지를 확인할 수 있는 정리이다. 만약 어떤 프로트 수 N=k ⋅ 2ⁿ + 1 (k는 홀수이고 k < 2ⁿ 이다)와 어떤 정수 a에 대하여

$a^{\frac {N-1}{2}}\equiv -1{\pmod {N}}$

이라는 관계식이 성립하면 N은 소수가 된다. 만약 N이 실제로 소수이면, 어떤 양의 정수 a가 다음의 관계식을 만족할 확률은 50%가 된다.

페팽 소수판별법

페팽 소수판별법 (Pépin's test)은 페르마 수에 대해서 적용할 수 있는 소수판별법으로, 다음과 같이 작동한다.

만약 어떤 페르마 수 $F_{n}=2^{2^{n}}+1$에 대하여

$3^{\frac {F_{n}-1}{2}}\equiv -1{\pmod {F_{n}}}$

이 성립하면 $F_{n}$은 소수가 되고, 아니면 $F_{n}$은 합성수가 된다. 페팽 소수판별법은 프로트의 정리의 개량된 부분정리라고도 할 수 있다.

뤼카 소수판별법 (결정론적)

결정론적인 뤼카 소수판별법 (Lucas Primality Test)은 다음과 같이 작동한다. 만약 1<a<n인 어떤 정수 a에 대하여

$a^{n-1}\equiv 1{\pmod {n}}$

그리고 n-1의 모든 소인수 q에 대하여

$a^{\frac {n-1}{q}}\not \equiv 1{\pmod {n}}$

이라면 n은 소수이다. 만약 위 조건들을 만족하는 a가 1과 n 사이에 존재하지 않으면 n은 합성수가 된다. 이 소수판별법은 n-1의 소인수들을 모두 알아야 하기 때문에 많이 쓰이지는 않지만, 포클링턴-레머 소수판별법의 기초가 된다.

포클링턴-레머 소수판별법

포클링턴-레머 소수판별법 (Pocklington-Lehmer Primality Test)은 다음과 같이 작동한다. 먼저, N−1을 AB 꼴로 분해한다. 이때 A와 B는 서로소이며 $A>{\sqrt {N}}$ 이고 A의 소인수분해를 알아야 한다.

만약 A의 각각의 소인수 p에 대하여

$a_{p}^{N-1}\equiv 1{\pmod {N}}$

그리고

$\gcd(a_{p}^{(N-1)/p}-1,N)=1$

을 만족하는 자연수 $a_{p}$가 A의 모든 소인수에 대하여 존재한다면 N은 소수가 된다. 만약 첫 번째 식의 값이 1이 아니거나 두 번째 식의 값이 1 또는 N이 아니라면 N은 합성수가 된다. 또한 브릴하트와 레머, 그리고 셀프리지는 A 부분이 $(N/2)^{\frac {1}{3}}$보다 커도 사용할 수 있는 개량된 알고리즘을 개발하였으며, 이 소수판별법과 쇼어의 알고리즘을 양자컴퓨터에서 재귀 반복하여 사용한다면 어떤 수를 소인수분해하는 데 걸리는 시간은 $O((\log {n})^{3}(\log {\log {n}})^{2}(\log {\log {\log {n}}}))$이 된다.

타원곡선 소수판별법

타원곡선 소수판별법 (Elliptic Curve Primality Proving, ECPP)은 타원곡선을 이용한 소수판별법이다. 애트킨 (Atkin)과 모레인 (Morain)이 개발한 알고리즘으로, 이 소수판별법을 이용하면 어떤 수가 소수인지 합성수인지를 $O((\log {n})^{5+\epsilon })$ 시간 안에 판별할 수 있게 된다. 다만 모든 자연수에 대해서 다항 시간 안에 소수판별이 끝나는지는 증명이 되지 않았으나, 컴퓨터에서 어떤 수가 소수인지를 확인할 때 쓰이는 알고리즘 중에서 많이 쓰이는 방법 중 하나이다.

APR 소수판별법

APR 소수판별법 (Adleman-Pomerance-Rumely Primality Test, APR Primality Test)은 어떤 수가 소수인지 합성수인지를 결정론적으로 확인할 수 있는 알고리즘이며 이 소수판별법의 개선된 방법인 APR-CL 소수판별법은 어떤 수가 소수인지 합성수인지를 $(\log {n})^{O({\log {\log {\log {n}}}})}$시간 안에 확인할 수 있다. 주로 컴퓨터에서 특정한 조건을 만족하는 수에 대해 많이 쓰는 알고리즘이다.

AKS 소수판별법

AKS 소수판별법 (Agrawal-Kayal-Saxena Primality Test, Cyclotomic AKS Test)은 결정론적이고, 무조건적이고, 모든 자연수에 대해 작동하고, 어떤 수가 소수인지 합성수인지를 다항 시간 안에 판별할 수 있는 유일한 알고리즘이다. 2002년에 발견되었으며, 이 발견을 한 세 저자들은 2006년 괴델상, 풀커슨상을 비롯한 많은 상들을 수상하였다. 원래 버전의 AKS 소수판별법은 어떤 수가 소수인지 합성수인지를 $O(\log ^{12}{n})$시간 안에 판별할 수 있으며, 후에 포머런스와 렌스트라에 의해 $O(\log ^{6}{n})$시간만에 어떤 수가 소수인지 합성수인지를 확인할 수 있는 개선된 AKS 소수판별법이 나오게 되었다. 또한 이 소수판별법의 개량된 방법 중 하나는 아그라왈의 추측이 맞다면 실행 시간이 $O(\log ^{3}n)$이 되며, 실행 시간이 다항 시간이기는 하지만 다른 소수판별법들보다 현저히 느리기 때문에 이 알고리즘은 실제로 큰 수를 소수판별할 때 많이 쓰이지 않는다.

같이 보기

• 소인수분해 알고리즘
• 유사소수
• 소수와 합성수