폴라드 p-1 소인수분해법

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

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

아이디어

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

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

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

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

알고리즘

계산 과정은 아래와 같다. 먼저 소인수를 찾고자 하는 합성수 [math]\displaystyle{ N }[/math]을 입력값으로 받는다.

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

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

적용 예

[math]\displaystyle{ N=7953983 }[/math]을 소인수분해하려고 한다. 여기서 [math]\displaystyle{ a=2, B=25 }[/math]라 놓고 계산을 시도한다.

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

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

작동 원리

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

두 소수 [math]\displaystyle{ p_1=2347, p_2=3389 (N=p_1p_2) }[/math]를 법으로 하는 모듈러 산술을 떠올려보자. 페르마의 소정리에 따르면 [math]\displaystyle{ a^E \equiv 1 \pmod {p_1, p_2} }[/math]가 성립할 충분조건은 각각 [math]\displaystyle{ p_1-1 \mid E, p_2-1 \mid E }[/math]이다.

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

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

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

거듭제곱의 지수 고르기

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

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

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

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

어떤 자연수[math]\displaystyle{ n }[/math]보다 큰 임의의 소수 [math]\displaystyle{ p }[/math]에 대해, [math]\displaystyle{ p-1 }[/math]이 [math]\displaystyle{ n }[/math]의 배수일 확률은 [math]\displaystyle{ \displaystyle \frac{1}{\phi(n)} }[/math]이다. 또, 이를 소수의 거듭제곱으로 한정하면, [math]\displaystyle{ p-1 }[/math]이 [math]\displaystyle{ q^r }[/math]의 배수일 확률은 [math]\displaystyle{ \frac{1}{q^{r-1}(q-1)} }[/math]이다.

이를테면 [math]\displaystyle{ p-1 }[/math]이 2의 배수일 확률은 1이다. 그러므로 [math]\displaystyle{ E }[/math]는 반드시 짝수여야만 하고, 시작점으로 [math]\displaystyle{ E_{\phi(n)=1}=2 }[/math]라 하자. 다음으로 3/4/6의 배수일 확률은 각각 2분의 1로, 2의 배수인 사건 다음으로 확률이 가장 높다. 다시 말해 [math]\displaystyle{ E_{\phi(n) \leq 2} =\operatorname{lcm}(E_{\phi(n)=1}, 3, 4, 6) =12 }[/math]라 놓으면 앞서 언급한 사건들을 모두 커버할 수 있다. 그 다음으로 확률이 높은 사건은 5/8/10/12의 배수인 경우로, 확률은 각각 4분의 1이다. [math]\displaystyle{ 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]\displaystyle{ E_{\phi(n) \leq 6} =\operatorname{lcm}(E_{\phi(n) \leq 4}, 7, 9, 14, 18) =2520 }[/math]이 된다.

이렇게 나아가서 특정 기준인 [math]\displaystyle{ B }[/math]에 대해 [math]\displaystyle{ n \mid p-1 }[/math]이 성립할 확률이 [math]\displaystyle{ 1/B }[/math] 이상인 [math]\displaystyle{ n }[/math]의 값들의 최소공배수로 [math]\displaystyle{ E }[/math]를 구성한다. 그러면 [math]\displaystyle{ \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]\displaystyle{ B }[/math]가 충분히 클 때, 위 식에서 큰 소수에 대해 [math]\displaystyle{ \frac{q}{q-1} \approx 1 }[/math]이므로, 보통은 편의상 [math]\displaystyle{ \displaystyle E =\operatorname{lcm}(2, 3, \cdots B) =\prod_{\text{primes}\ q \leq B} q^{\lfloor \log_{q} B \rfloor} }[/math]로 식을 간단히 잡는다.

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

한계점

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

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

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

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

변칙 알고리즘

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

지수 바꾸기

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

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

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

두 단계 분할

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

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

구체적인 방법은 이와 같다:

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