페르마의 인수분해(Fermat's factorization)

 

https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

Fermat's factorization method - Wikipedia

정수론 시간에 잠깐 배웠고, 문제 푸느라 써먹긴 했지만 정확한 원리는 모르는 페르마의 인수분해.

 

그 원리를 알아보고 구현해보자.

 

원리

---

페르마의 인수분해는 홀수인 합성수 N에 대해 ,$\sqrt N$ 과 근접한 두 인수를 찾을 수 있는 방법이다.

CTF에서는 서로 근접한 p, q로 만들어진 n을 주고 페르마의 인수분해를 이용해서 p, q를 찾는 과정을 이용한다. 페르마 인수분해는 두 인수가 비슷할 때 빠른 인수분해 방법을 제시하기 때문이다.

 

페르마의 인수분해는 합차공식 $(a+b)(a-b) = a^2 - b^2$ 을 기반으로 한다.

어떤 수 $N$이 $(a+b)(a-b)$가 되는 a, b를 찾으면 $(a+b)$와 $(a-b)$로 인수분해 된다고 볼 수 있다.

 

$N = pq$라고 할 때. $s^2 - t^2$ 꼴에서 $s = (p+q)/2$, $t = (p-q)/2$라고 하면 $N = s^2 - t^2$이 성립한다.

$\therefore s^2 - N = t^2$ 이다. s와 t를 구하기 위해서 $s = [\sqrt N]$ 이라 하고 s를 1씩 증가하면서 $s^2 - N$의 값이 제곱수가 되는지 검사한다. $s^2 - N$이 제곱수이면 s와 t를 찾을 수 있고, $(s+t)$, $(s-t)$를 인수로 가진다.

 

이 알고리즘은 완벽히 소인수분해 하기보다는 서로 짝인 인수를 찾는 것에 가까워보인다.

 

구현

---

 

from gmpy2 import *

def fermat_factor(n):
	assert n % 2 != 0

	s = isqrt(n)
	t2 = square(s) - n

	while not is_square(t2):
		s += 1
		t2 = square(s) - n
	p = s + isqrt(t2)
	q = s - isqrt(t2)
	return int(p), int(q)

python으로 구현하였다.

s를 $\sqrt N$으로 두고 그러면 t는 $\sqrt {s^2 - n}$이다. 계산을 위해서 $t^2$으로 $s^2 - n$이라고 두고 t값이 필요할 경우에 sqrt()를 취한다.

$t^2(s^2 - n)$가 제곱수가 아닌 동안 s를 1 증가시키고 t2에 다시 값을 넣는 것을 반복한다.

 

반복문을 빠져나오면 t2가 제곱수가 되는 s와 t를 찾았다.

p는 s + t이고, q는 s - t 가 된다.

 

 

왜 p와 q가 비슷한 수이면 계산하기 쉬운걸까?

시간에 영향을 주는 부분은 while 문이고, 숫자가 비슷하다는 것은 p와 q가 $\sqrt N$에 가깝다는 것을 말한다. 

 

[1] S.-H. Jung and S.-H. Jung, “A Consideration on Verification and Extension of Fermat’s Factorization,” Journal of the Korea Institute of Information Security & Cryptology, vol. 20, no. 3, pp. 3–8, Jun. 2010.

 

직관적으로 볼 때, 우리는 s가 $\sqrt N$ 부터 시작해서 s + t, s - t 를 찾아가는데, 당연히 s+t, s-t에 해당하는 값 p, q가 $\sqrt N$에 가까이 있으면 반복이 적다.