Number Theory - 5.4 페르마-크렡칙 소인수분해

페르마 소인수분해

인수분해 하려는 홀수 $n$에 대해, $n=x^2-y^2$ 를 만족하는 수 $x,y$를 찾는 것은 인수분해를 하는것과 동치이다.

짝수라면 $2$로 계속 소거해간다.

$$ \because n=(x+y)(x-y) $$

만약 $n=ab(1 \le b \le a)$ 라면,

$$ \begin{aligned} n&=ab\\ &=\Bigl(\dfrac {a+b}2\Bigr)^2-\Bigl(\dfrac {a-b}2\Bigr)^2 \end{aligned} $$

로 역도 성립한다.

이 때, $n$이 홀수이므로 $a, b$ 모두 홀수이다.

---

$n=x^2-y^2$ 를 찾는 과정은 $x^2-n=y^2$ 꼴을 찾는 과정이다.

$k^2 \ge n$인 $k$ 부터 $k$ 를 $1$씩 늘려가며 $k^2-n$ 이 완전제곱수가 되는 경우를 찾는다.

$$ \begin{gathered} k^2-n \\ (k+1)^2-n \\ (k+2)^2-n \\ \vdots \end{gathered} $$

이는 인수를 찾지 못하면 궁극적으로 $\left( \dfrac {n+1}2 \right)^2-n=\left( \dfrac {n-1}2 \right)^2$ 에 도달하고,

인수 $n, 1$ 을 찾아내고 종료된다. 이 경우 $n$은 소수이다.

페르마 소인수분해 일반화

$n=x^2-y^2$ 꼴에서 $x^2-y^2$ 이 $n$의 배수가 되는 $x, y$를 조사한다. 즉,

$$ x^2 \equiv y^2 \pmod n $$

$d=gcd(x-y,n)$ 혹은 $d=gcd(x+y,n)$ 이라 하자.

$d$는 $n$의 약수지만, $1 < d < n$ 을 만족하는 진약수인지가 관건이다.

$n$이 두 소수 $p,q$의 곱일 때, $d \in \{1,p,q,pq\}$

$$ \begin{matrix} x^2 \equiv y^2 \pmod n\\ \Downarrow\\ pq \mid (x+y)(x-y) \end{matrix} $$

유클리드 보조정리에 의해 $p$와 $q$는 각각 $(x+y), (x-y)$ 중 하나를 나눈다.

$p \mid x+y,~q \mid x+y$ 이면 $n \mid x + y$ 이다.

그럼 $x+y \equiv 0 \pmod n$ 이 되어서 $d=gcd(x+y,n)=n$ 이 되어서 $1 < d < n$ 을 만족하는 진약수를 찾을 수 없다.

$p \mid x-y,~q \mid x-y$이면 유사하게 $d$ 가 진약수가 되지 못한다.

결국 $p$와 $q$가 각각 $x+y, x-y$ 를 하나씩 나누는 경우만 $d$가 $n$의 진약수가 된다.

이 때의 $d$는 $d=p$ 혹은 $d=q$ 이다.

정리하자면, $x^2 \equiv y^2 \pmod n$ 인 정수 $x, y$ 를 찾으면 $gcd(x+y,n)$과 $gcd(x-y,n)$ 이 $n$의 진약수가 되어 인수분해를 진행할 수 있다.

이를 만족하는 $x$와 $y$를 찾는 방법은 $2189$의 배수에 가까운 제곱수를 조사하면서 대충 뒤져보는 것인데, 그래서 문제를 풀 땐 폴라드 로 소인수분해 같은것과 비교하면 별 쓸모가 없다.

$n$이 세개 이상의 소인수를 가질 땐, 위와 같은 방법으로 찾은 $d$가 $n$의 진약수라는 보장이 없다.

그래서 PS에선 쓸모없다.

크렡칙 소인수분해

생략

이 또한 PS에는 쓰이지 않는다.