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

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

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

아이디어

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

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

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

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

알고리즘

계산 과정은 아래와 같다. 먼저 소인수를 찾고자 하는 합성수 $N$을 입력값으로 받는다.

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

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

적용 예

$N=7953983$을 소인수분해하려고 한다. 여기서 $a=2,B=25$라 놓고 계산을 시도한다.

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

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

작동 원리

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

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

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

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

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

거듭제곱의 지수 고르기

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

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

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

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

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

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

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

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

한계점

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

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

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

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

변칙 알고리즘

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

지수 바꾸기

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

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

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

두 단계 분할

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

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

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

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