Fermat’s Factorization Method

By | 2010/01/03

  이번 방학 목표 중 하나로 이산수학 책 한 권 제대로 공부하는 것입니다. 2학년 1학기에 이산수학 과목을 들었지만 무언가 부족하다는 느낌이 강했기에 방학 때 공부해보고 싶었습니다. 하지만 게을러서 지금까지 대충대충 보고 넘어왔더니 여전히 부족하네요. 그래서 독하게 이번 방학 때는 꾸준히 할 생각입니다. 대신 중요한 것이나 재미있었던 것은 따로 블로그에 올려 후에 검색하기 편하게 할 생각입니다.

  소인수분해 방법으로 책에서 소개한 것은 일반적인 방법인 하나씩 소수를 찾아 나눠가는 방법과 함께 페르마 방법(Fermat’s Factorization Method)이라는 것을 소개하였습니다. 알고리즘을 이해하고 나서는 ‘이런 무식한 방법이 있나.’하는 생각이 들었지만 그래도 없는 것보다는 좋지 않나 하는 생각이 들었습니다.

  알고리즘 방법은 다음과 같습니다.

  그리고 이를 Sagemath를 이용해서 구현해보았습니다.

c038

http://nosyu.iptime.org:8000/home/pub/0

  1: def FFM(n):
  2:   a = 0
  3:   b = 0
  4:   x = ceil(sqrt(n))
  5:   y = 0
  6:   while (pow(x,2) - pow(y,2)) > n:
  7:       y = y + 1
  8:       if (pow(x,2) - pow(y,2)) < n:
  9:           x = x + 1
 10:           y = 1
 11:       else :
 12:           if (pow(x,2) - pow(y,2)) == n:
 13:               a = x - y
 14:               b = x + y
 15:   return (a,b)

  위의 링크는 제가 개인적으로 쓰는 서버라서 링크가 깨져있는 날이 더 많을 것입니다.

  여하튼 이 방법을 사용하면 값을 구할 수 있다는 것을 확인하였습니다.

  두 인수의 차이가 크지 않을 때 유리한 방법이라고 하니 훗날 필요 있을 때 기억을 되살릴 수 있는 그런 글이 되기를 바랍니다.

참조

Leave a Reply