📂정수론

폴라드 p-1 소인수분해 알고리즘 증명

알고리즘 ¹

준소수 $N$ 이 주어져있다고 하자. $p$ 가 스무스 소수라면 $N$ 의 소인수분해 $N = pq$ 는 다음과 같이 구할 수 있다.

---

Step 1.

$a := 2$ 와 $L := 1$ 을 정한다.

---

Step 2.

$d := \gcd ( a^{L} - 1 , N )$ 를 계산한다.

---

Step 3.

$1< d < N$ 이면 $N$ 의 약수 $d = p$ 를 구한 것이므로 끝이다. 그 외의 경우엔 $L := (L+1)!$ 과 같이 업데이트한다. $L$ 이 너무 큰 경우엔 $L := 1$ 로 되돌리고 $a : = a+ 1$ 과 같이 업데이트한다. 그 후 Step 2로 돌아간다.

설명

폴라드 $p-1$ 소인수분해 알고리즘은 폴리그-헬맨 알고리즘처럼 스무스 소수의 약점을 이용한다. 소수 하나가 약점이 되어서 소인수분해 문제가 쉽게 풀려버리는 것이다. 이 공격법 때문이라도 소인수분해 문제의 어려움을 이용한 암호체계들은 비밀 키로써 스무스 소수를 사용할 수 없게 된다.

원칙적으로 Step 1처럼 $a=2$ 로 시작하고 Step 2처럼 $L = n!$ 을 사용할 필요는 없다. 다만 $a$ 로 처음부터 큰 숫자를 할 이유가 딱히 없고, $p$ 가 스무스 하다면 $d := \gcd ( a^{L} - 1 , N )$ 를 성공적으로 계산할 확률이 높아서 그렇게 쓸 뿐이다.

증명

$$(p-1) \mid L \\ (q-1) \nmid L$$ $p$ 는 스무스하므로 $L = n!$ 에 대해서 위의 조건을 만족시키기 쉽다고 가정한다. 이는 다시 말해 어떤 $i,j \in \mathbb{Z}$ 와 $k \in \mathbb{N}$ 에 대해 다음이 성립한다는 것이다. $$\begin{align*} L =& i ( p -1 ) \\ L =& j ( q -1 ) + k \end{align*}$$

페르마의 소정리: 소수 $p$ 와 서로소인 정수 $a$ 에 대해, $a^{p-1} \equiv 1 \pmod{p}$

$\pmod{p}$ 에서는 $$\begin{align*} a^{L} & \equiv a^{( p - 1 ) i } \\ & \equiv 1^{i} \\ & \equiv 1 \pmod{p} \end{align*}$$ $\pmod{q}$ 에서는 $$\begin{align*} a^{L} & \equiv a^{( q - 1 ) j + k } \\ & \equiv 1^{j} a^{k} \\ & \equiv a^{k} \pmod{q} \end{align*}$$ 여기서 $k \ne 0$ 이므로 어지간한 경우엔 $a^{k} \ne 1 \pmod{q}$ 일 가능성이 높다. 이는 다시 말해 $$p \mid a^{L} -1$$

$$q \nmid a^{L} -1$$ 이는 $p$ 가 $a^{L} -1$ 의 약수라는 말인데, $p$ 는 $N$ 의 약수이기도 하므로 두 수의 최대공약수를 계산하면 $$p = \gcd \left( a^{L} - 1 , N \right)$$

■

같이보기

• 소인수분해

소인수분해 문제의 어려움을 이용한 보안 알고리즘

• RSA 공개 키 암호체계
• 골드바서-미칼리 확률 키 암호체계

소인수분해 문제에 대한 공격 알고리즘

• 폴라드 p-1 소인수분해 알고리즘
• 준소수의 소인수분해 문제가 쉽게 풀리는 조건