https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
Fermat's factorization method - Wikipedia
From Wikipedia, the free encyclopedia Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: N = a 2 − b 2 . {\displaystyle N=a^{2}-b^{2}.} That difference is algebr
en.wikipedia.org
정수론 시간에 잠깐 배웠고, 문제 푸느라 써먹긴 했지만 정확한 원리는 모르는 페르마의 인수분해.
그 원리를 알아보고 구현해보자.
원리
페르마의 인수분해는 홀수인 합성수 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$에 가깝다는 것을 말한다.
직관적으로 볼 때, 우리는 s가 $\sqrt N$ 부터 시작해서 s + t, s - t 를 찾아가는데, 당연히 s+t, s-t에 해당하는 값 p, q가 $\sqrt N$에 가까이 있으면 반복이 적다.
