폴라드 p-1 소인수분해법 문서 원본 보기

'''폴라드 p-1 소인수분해법'''(Pollard's p-1 factorization algorithm)은 큰 수를 [[소인수분해]]하는 방법으로, 1974년 존 폴라드(John Pollard)가 고안하였다. 이 소인수분해법은 어떤 자연수의 소인수 <math>p</math>에 대해 <math>p-1</math>이 작은 소인수들의 곱으로 표현되거나, 특정한 약수를 알고 있을 때 적용이 잘 된다.

일반적으로 큰 수에서는 이보다 좀 더 빠른 [[렌스트라 타원 곡선 소인수분해법]]이나 [[이차 체]] 등을 더 많이 이용한다.

== 아이디어 ==
합성수 <math>N</math>이 주어져 있고, 이 수의 소수인 약수 <math>p</math>가 알고 싶은 값이다. 찾고가 하는 소수와 서로소인 자연수 <math>a</math>를 아무거나 지정한다.

[[페르마의 소정리]]가 본 알고리즘의 기본 아이디어이다. 이 정리의 관계식을 불러오고, 합동식의 양 변에 특정 거듭제곱을 취한다.
<math>a^{p-1} \equiv 1 \pmod p \Rightarrow a^{K(p-1)} \equiv 1 \pmod p</math>

이를 다시 서술하면, <math>p-1 \mid E \Leftrightarrow E=K(p-1)</math>인 자연수 <math>E</math>에 대해 <math>p \mid a^E-1</math>이 성립하며, 동시에 <math>p \mid N</math>이므로 <math>p \mid \gcd(a^E-1, N)</math>임을 이끌어낼 수 있다. 여기서 <math>a, E</math>는 우리가 임의로 지정하는 자연수로, 이들 수를 이용해 계산한 값과 주어진 자연수의 [[최대공약수]]를 구하는 것이 알고리즘의 핵심이다.

실제 계산 과정에서는 <math>p</math>의 값을 모르는 채로 진행한다. 이때 소인수분해하려는 자연수의 특정 소인수가 <math>p-1 \mid E</math> 조건에 최대한 잘 걸려들게 하려면 <math>E</math>를 충분히 큰 수로 잡아야 할 것이다. 그러면 <math>Q_0=a^E-1</math>의 값 자체는 무지막지하게 커지는데, 여기서 <math>Q=Q_0 \mod N</math>이라 하면 <math>\gcd(Q, N)=\gcd(Q_0, N)</math>이 성립하므로, 거듭제곱은 법 <math>N</math> 내에서 [[모듈러 산술]]로 계산하면 된다.

== 알고리즘 ==
계산 과정은 아래와 같다. 먼저 소인수를 찾고자 하는 합성수 <math>N</math>을 입력값으로 받는다.

* <math>N</math>과 서로소인 <math>a</math>를 아무 값이나 지정한다. 보통은 2 또는 3을 많이 고른다.
* (◇) 거듭제곱의 지수를 셈할 기준값 <math>B</math>를 고른다.
* <math>\displaystyle E =\operatorname{lcm}(2, 3, \cdots B) =\prod_{\text{primes}\ q \leq B}q^{\lfloor \log_q B \rfloor}</math>를 셈한다. (자세한 설명은 아래 "지수 고르기" 문단 참고)
* <math>Q=a^E-1 \mod N</math>을 셈한다.
* <math>g=\gcd(Q, N)</math>을 셈한다.
* <math>1 < g < N</math>이면 값을 출력한다. <math>g</math>가 소수이면 계산 종료, 합성수이면 이 값을 다시 소인수분해한다.
* <math>g=1</math>이면 <math>B</math>의 값을 올려서 (◇) 단계로 돌아가거나 "실패"를 출력한다.
* <math>g=N</math>이면 <math>B</math>의 값을 내려서 (◇) 단계로 돌아가거나 "실패"를 출력한다.

아무리 <math>B</math>의 값을 올려도 비자명한 약수를 찾지 못한다면, <math>p-1</math>이 어떤 큰 소수를 약수로 가진다는 것을 의미한다. 마지막 줄의 상황을 만나면 대부분 <math>B</math>의 값을 내리는 걸로 성공한다. 그런데 가끔 기준값을 올리거나 내리기를 몇 번이고 반복해도 합성수를 쪼개지 못하는 경우도 나오는데, 이는 아래 문단에서 후술.

=== 적용 예 ===
<math>N=7953983</math>을 소인수분해하려고 한다. 여기서 <math>a=2, B=25</math>라 놓고 계산을 시도한다.

* <math>E =\operatorname{lcm}(2, 3, \cdots 25) =26771144400</math>
* <math>Q=2^E-1 \mod N</math>을 셈한다. 지수 값이 매우 크지만 [[거듭제곱 계산법]]에 적힌 방법으로 수월하게 계산할 수 있다.
** <math>2^n = \begin{cases} (2^{n/2})^2\ (n\ \text{even}) \\ 2 \cdot (2^{(n-1)/2})^2\ (n\ \text{odd}) \end{cases}</math>
** <math>Q=77451</math>
* <math>g=\gcd(Q, N) = \gcd(77451, 7953983) = 2347</math>
* 따라서 주어진 수의 약수인 2347을 찾았고, 이에 따라 <math>N=2347 \cdot 3389</math>임을 알 수 있다.

알고리즘을 종료한 후, 두 약수 모두 소수임을 확인하면 소인수분해는 끝난다.

=== 작동 원리 ===
앞선 예시를 들어보면 아래와 같이 서술할 수 있다.

두 소수 <math>p_1=2347, p_2=3389 (N=p_1p_2)</math>를 법으로 하는 모듈러 산술을 떠올려보자. [[페르마의 소정리]]에 따르면 <math>a^E \equiv 1 \pmod {p_1, p_2}</math>가 성립할 충분조건<ref>필요충분조건이 아닌 이유는 법 <math>p</math>에 대한 <math>a</math>의 [[위수 (정수론)|위수]]가 <math>p-1</math>보다 작을 수 있기 때문이다. 즉 <math>a \equiv b^{m} \pmod p, p-1=mn</math>인 <math>b, m, n</math>이 존재하면 <math>a^n \equiv b^{p-1} \equiv 1 \pmod p</math>가 된다.</ref>은 각각 <math>p_1-1 \mid E, p_2-1 \mid E</math>이다.

한편 <math>p_1-1 =2346 =2 \cdot 3 \cdot 17 \cdot 23, p_2-1=3388 =2^2 \cdot 7 \cdot 11^2</math>이다. 그러면 <math>p_1-1 \mid E</math>이지만 <math>p_2-1 \mid E</math>는 성립하지 않는다. 위에서 계산한 <math>E=\operatorname{lcm}(1, 2, \cdots 25)</math>는 23 이하의 소수들의 배수이지만 11의 제곱 항은 포함하지 않기 때문이다.

이 때문에 <math>2^E \equiv 1 \pmod{p_1}</math>은 필연적으로 성립하지만 <math>2^E \equiv 1 \pmod{p_2}</math>는 성립하지 않는다. 이를 다시 쓰면 <math>Q=2^E-1 \mod N =77451</math>에 대해 <math>p_1 \mid Q, p_2 \nmid Q</math>이므로, 주어진 수의 비자명한 약수 <math>p_1=\gcd(Q, N)</math>을 추출하고 여인수인 <math>p_2=N/p_1</math>을 발견하게 된다.

폴라드 소인수분해법은 이처럼 구하고자 하는 소인수에 대한 합동식을 만족하는지 여부를 이용한다. <math>Q</math>의 값이 특정 소인수(<math>p_1</math>)로 나누어 떨어지면서 다른 소인수(<math>p_2</math>)로 나누어 떨어지지 않게 되면, 알고리즘은 성공한다.

== 거듭제곱의 지수 고르기 ==
앞서 계산에 지정할 지수인 <math>E</math>는 가급적 큰 수를 골라야 목적을 달성할 수 있다는 사실을 알았다. 좀 더 정확히는 <math>p-1 \mid E</math> 조건식이 성립하는 <math>p</math>를 충분히 많이 품어야 하는데, 이는 곧 <math>E</math>가 '''아주 많은 약수'''를 가져야 한다는 이야기가 된다.

이를테면 <math>E_1 =10000 =2^4 \cdot 5^4</math>보다는 <math>E_2 =10080 =2^5 \cdot 3^2 \cdot 5 \cdot 7</math>과 같이 다양하고 자잘한 소인수들의 곱으로 이루어진 수가 적합하다고 할 수 있다.

이 조건을 생각해보면 <math>E=m!</math>, 즉 [[계승]]에 해당하는 수를 잡을 때 많은 약수를 끌어모을 수 있을 것이나, 이보다 좀 더 효율적인 선정 방법이 하나 있다. 바로 [[최소공배수]]를 이용하는 것이다.

<math>p</math>의 값을 찾으려는 우리 입장에서는 <math>p-1</math>이 어떤 수의 배수인지 모른다. 하지만 <math>n \mid p-1</math>이 성립할 확률이 높은 <math>n</math>의 값들로 <math>E</math>를 구성한다면 ''높은 확률로'' <math>p-1 \mid E</math> 조건식을 만족할 거라 기대할 수 있다.

어떤 자연수<math>n</math>보다 큰 임의의 소수 <math>p</math>에 대해, <math>p-1</math>이 <math>n</math>의 배수일 확률은 <math>\displaystyle \frac{1}{\phi(n)}</math>이다. <ref><math>n, p</math>는 서로소이기 때문에 [[오일러 피 함수]] 항이 들어간다.</ref> 또, 이를 소수의 거듭제곱으로 한정하면, <math>p-1</math>이 <math>q^r</math>의 배수일 확률은 <math>\frac{1}{q^{r-1}(q-1)}</math>이다.

이를테면 <math>p-1</math>이 2의 배수일 확률은 1이다.<ref>우리가 주목할 부분은 어떤 합성수가 '''큰 소수'''의 곱으로만 이루어져 있는 경우만을 생각한다. 작은 소인수들은 직접 나누기로 쉽게 찾을 수 있기 때문. 따라서 2, 3, 5, 7, …과 같은 자잘한 소수들은 <math>p</math>의 후보로 고려하지 않는다. </ref> 그러므로 <math>E</math>는 반드시 짝수여야만 하고, 시작점으로 <math>E_{\phi(n)=1}=2</math>라 하자. 다음으로 3/4/6의 배수일 확률은 각각 2분의 1로, 2의 배수인 사건 다음으로 확률이 가장 높다. 다시 말해 <math>E_{\phi(n) \leq 2} =\operatorname{lcm}(E_{\phi(n)=1}, 3, 4, 6) =12</math>라 놓으면 앞서 언급한 사건들을 모두 커버할 수 있다. <ref>어떤 수가 <math>a, b</math>의 배수가 되는 두 사건의 곱사건은 <math>\operatorname{lcm}(a, b)</math>의 배수인 사건이다. 즉 곱이 아닌 최소공배수를 기준으로 셈한다.</ref>그 다음으로 확률이 높은 사건은 5/8/10/12의 배수인 경우로, 확률은 각각 4분의 1이다. <math>E_{\phi(n) \leq 4} =\operatorname{lcm}(E_{\phi(n) \leq 2}, 5, 8, 10, 12) =120</math>. 또, 7/9/14/18의 배수일 확률은 6분의 1로, 이들 값들을 다시 포함하면 <math>E_{\phi(n) \leq 6} =\operatorname{lcm}(E_{\phi(n) \leq 4}, 7, 9, 14, 18) =2520</math>이 된다.

이렇게 나아가서 특정 기준인 <math>B</math>에 대해 <math>n \mid p-1</math>이 성립할 확률이 <math>1/B</math> 이상인 <math>n</math>의 값들의 최소공배수로 <math>E</math>를 구성한다. 그러면 <math>\displaystyle E =\operatorname{lcm}(n_1, n_2, \cdots n_k) (\phi(n_i)\leq B) =\prod_{\text{primes}\ q \leq B+1} q^{\lfloor \log_{q} \frac{qB}{q-1} \rfloor}</math>라는 결론에 도달한다. 그런데 사실 <math>B</math>가 충분히 클 때, 위 식에서 큰 소수에 대해 <math>\frac{q}{q-1} \approx 1</math>이므로, 보통은 편의상 <math>\displaystyle E =\operatorname{lcm}(2, 3, \cdots B) =\prod_{\text{primes}\ q \leq B} q^{\lfloor \log_{q} B \rfloor}</math>로 식을 간단히 잡는다.

일반적으로 계승과 최소공배수, 즉 <math>A!=2\cdot 3 \cdot \cdots \cdot A, L(B)=\operatorname{lcm}(2, 3, \cdots B)</math> 두 값의 크기가 비슷할 때, <math>p-1 \mid A!</math>을 만족하는 소수보다는 <math>p-1 \mid L(B)</math>를 만족하는 소수들이 더 많다.

== 한계점 ==
이 소인수분해법의 아이디어는 <math>p</math>가 매우 큰 소수이더라도 <math>p-1</math>은 좀 더 작은 인수들의 곱으로 나타낼 수 있자는 데에서 고안되었다. 하지만 이 가운데에서도 커다란 소수가 들어가 있으면 <math>p-1 \mid E</math> 조건이 들어맞기 매우 힘들다. 가장 운이 나쁜 경우는 바로 합성수가 [[안전 소수]]들의 곱으로 이루어져 있는 경우다.

안전 소수란 <math>p=2q+1</math>의 꼴로 표현되는 소수로, 여기서 <math>q</math>는 [[소피 제르맹 소수]]이다. <math>q=\frac{p-1}{2}</math>가 소수이면 <math>p-1 \mid L(B)</math>가 성립하기 위한 조건은 <math>B \geq q</math>인데, 이 경우 직접 나누기보다도 계산량이 더 많이 들어간다.

예를 들어 <math>N=31910017=p_1p_2, p_1=4079, p_2=7823</math>인 경우를 생각해보다. 두 소인수는 모두 안전 소수이다. <math>n < 2039</math>이면 <math>p_1-1 \mid L(B) \text{ or } p_2-1 \mid L(B)</math> 둘 중 어느 하나도 만족할 수 없으며, 결국 소인수를 찾을 수 없게 된다. 만약 어느 한쪽이 찾기 쉬운 소수라면, 다른 한쪽이 안전 소수이더라도 알고리즘은 비교적 쉽게 성공한다.

이런 특징을 가진 소수들이 안전 소수라 불리는 이유는 소수 암호에서 주어진 합성수의 소인수들을 이 소인수분해법으로 간파하기 매우 어렵기 때문이고, 이는 곧 '''암호의 보안 수준이 높다'''는 의미로 통한다. 소수 암호와 관련된 자세한 내용은 [[RSA]] 문서 참고.

== 변칙 알고리즘 ==
<math>E=L(B)=\operatorname{lcm}(2, 3, \cdots B), Q=a^E-1 \mod N</math>을 셈하는 것이 기본 과정이지만 여기에서 계산 방식을 바꾸거나, 효율을 한층 개선하는 방법이 있다.

=== 지수 바꾸기 ===
앞서 <math>E</math>의 값은 최소공배수 연산으로 고르는 것이 보통 효율적이라고 밝혔으나, 가끔은 [[계승]]을 기준으로 할 때 더 쉽게 풀리기도 한다. 그 특수한 예로 <math>N=3060774511=p_1p_2, p_1=65537, p_2=46703</math>을 들 수 있다.

먼저 <math>p_1-1=2^{16}, p_2-1=2 \cdot 19 \cdot 1229</math>이다. 그러면 <math>p_1-1 \mid L(B)</math>이 성립하려면 <math>B \geq 2^{16}</math>이어야 하고, <math>p_2-1</math>의 경우 <math>B \geq 1229</math>이다. 하지만 이 경우는 계승으로 다시 설정하면 보다 쉽게 풀린다.

<math>E=18!</math>로 잡으면 <math>2^{16} \mid 18!</math>이므로 <math>p_1-1 \mid E</math> 조건식에 걸려들고, 본 알고리즘은 성공한다. <math>18! \ll L(1229)</math>임을 생각하면 이쪽이 훨씬 쉬운 경로임을 알 수 있다.

=== 두 단계 분할 ===
임의의 소인수에 대해 <math>p-1=r_1r_2 \cdots r_k</math> 꼴로 소인수분해하고, <math>r_i (1 \leq i \leq k)</math>는 소수 또는 소수의 거듭제곱을 크기 순으로 배열한 값이라고 하자. 그러면 상당한 경우 가장 큰 항인 <math>r_k</math>는 그 다음으로 큰 <math>r_{k-1}</math>보다 훨씬 큰 경향을 보인다. 가령 <math>187477-1=2^2 \cdot 3 \cdot 17 \cdot 919</math>와 같이 끝 항이 굵직하게 남는 경우와, <math>134597-1=2^2 \cdot 7 \cdot 11 \cdot 19 \cdot 23</math>과 같이 자잘한 소인수들로 나뉘는 경우 중 전자가 빈번하게 나타난다. 사실 큰 수로 갈수록 후자와 같은 특징을 보이는 소인수를 찾을 수 있다면 운이 아주 좋은 경우다.

위에서 소개한 기본 알고리즘은 <math>B \geq r_k</math>를 만족하도록 기준치 <math>B</math>의 값을 충분히 올리는 것이다. 하지만 소인수분해 성공을 위한 최소한의 기준치가 너무 높다 싶을 때, 기본 목표를 먼저 <math>B_1 \geq r_{k-1}</math>까지만으로 낮춘 다음, 다른 방법으로 <math>B_2 \geq r_k</math>까지 빠르게 도약할 수 있다면 계산 시간을 단축할 수 있을 것이다.

구체적인 방법은 이와 같다:
* 먼저 기본 알고리즘과 같이 첫째 목표치 <math>B_1</math>과 그에 따른 지수를 셈한다. 
* <math>\displaystyle E=\prod_{\text{primes}\ q \leq B_1}q^{\lfloor \log_{q}B_1 \rfloor}</math>
* 마찬가지로 <math>Q_0=a^E-1 \mod N</math>을 셈한다.
* 여기까지가 1단계(stage 1)이다. 만약 <math>\gcd(Q_0, N)</math>을 셈해서 운 좋게 약수를 찾았다면, 여기서 알고리즘을 종료할 수 있다. 약수를 찾지 못했다면, 2단계(stage 2)로 넘어간다.
* <math>H =a^E \mod N (=Q_0+1)</math>을 저장하고, 둘째 목표치인 <math>B_2</math>를 상정한다.
* <math>B_1 < q \leq B_2</math>를 만족하는 소수<ref>경우에 따라서는 (밑이 큰) 소수의 거듭제곱도 포함할 수도 있다.</ref> 목록을 작성하고 이를 오름차순으로 정렬한다.
* <math>H^2, H^4, H^6, \cdots \mod N</math>의 값들을 계산해서 메모리에 저장해둔다. 이 목록은 길수록 좋다(즉 저장할 메모리를 많이 확보하면 좋다)
* 앞서 작성한 목록<math>\{q_n\} (1 \leq n \leq M)</math> 중 첫째 항을 꺼내서 <math>S_1=H^{q_1} \mod N, Q_1=S_1-1</math>을 계산한다.
* 이어서 <math>d_n = q_{n+1}-q_n</math>을 셈하고, 해당 값에 대응하는 <math>H^{d_n} \mod N</math>의 값을 메모리에서 불러온 다음 <math>S_{n+1}=H^{q_{n+1}}=S_nH^{d_n} \mod N, Q_{n+1}=Q_n(S_{n+1}-1) \mod N</math>을 차례대로 셈한다.
* 마지막 항까지 계산해서 <math>\displaystyle Q_M=\prod_{1 \leq n \leq M}(H^{q_n}-1) \mod N</math>의 값을 구한다.
* <math>\gcd(Q_M, N)</math>을 셈해서 비자명한 약수를 찾게 되면 알고리즘은 성공한다.

{{각주}}
{{수론 알고리즘}}
[[분류:알고리즘]]