폴라드 p-1 소인수분해 알고리즘 증명
알고리즘 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) $$
■
같이보기
소인수분해 문제의 어려움을 이용한 보안 알고리즘
소인수분해 문제에 대한 공격 알고리즘
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p133~135. ↩︎