#4-5-4 The Art of Computer Programming - 준수치적 알고리즘

이번절은 이름도 익숙한 '소인수분해'에 대한 절이다.

꽤 긴 내용을 담고 있고 정리 및 증명도 많이 나온다.

 

지금까지 알려진 바로는 큰 수 n을 인수분해하는 것이 m, n 두 수의 최대공약수를 구하는 것보다 훨씬 어렵다.

그러므로 큰 수의 인수분해는 왠만하면 피하는 게 좋다.

하지만 인수분해를 빠르게 하는 몇가지 방법들이 있기에, 이번절에서 그것들을 소개한다.

 

1. 분할분해 : n mod p!= 0 이거나 n/p <= p가 될 때까지 mod 연산을 지속하면 구할 수 있다.

2. 유사 순환마디를 이용한 인수분해 : 무작위 사상들에 대한 값으로 mod 연산을 해서 구함.

3. 페르마의 방법 : x = (u+v)/2, y=(v-u)/2, N=x^2-y^2, 0 <=y <x <=N을 만족하는 x, y를 구하는 방법.

 

그 외에도 몇가지 방법들이 소개는 되지만 이해가 안돼서 패스.

 

오늘은 여기까지!