정보과학 (Informatic)/알고리즘 (3) 썸네일형 리스트형 Pollard's rho 알고리즘 소인수분해를 해야한다. 그런데 대상인 수가 18자리의 거대한 수라면?! 가볍게 소인수분해를 할 때 사용하는 $O(\sqrt{N})$ 의 알고리즘으로는 어림도 없다. 만약 더 빠른 알고리즘의 필요성을 느꼈다면 아래의 Pollard's rho 알고리즘이 좋은 대안이 될 수 있다. Pollard's rho algorithm Pollard's rho algorithm은 영국의 수학자 John Pollard가 1975년 고안한 알고리즘으로 평균적으로 대략 $O(N^{1/4})$ 정도에 동작한다. 다만 언제나 $O(N^{1/4})$ 인 것은 아닌데, 이는 휴리스틱 알고리즘이기 때문이다. 난수와 관련된 부분에서 의사난수를 사용하기 때문에 늘 $O(N^{1/4})$ 임이 보장되지는 않는다. N을 소인수분해를 한다고 하.. Miller-Rabin primality test (밀러-라빈 소수판정법) "2,305,843,009,213,693,951을 소인수분해 하시오." 하고 싶어도 못할 것이다. 이 수는 소수이기 때문이다. 그러나 흔히 알려진 $O(\sqrt{N})$ 알고리즘을 사용하기에도 시간이 부족해 보인다. 이 경우 밀러-라빈 소수판정법을 사용하면 어마어마하게 단축된 시간에 소수인지 아닌지 여부를 판단할 수 있다. Miller-Rabin pirmality test 밀러 라빈 소수판정법은 하나의 $lemma$ 를 통하여 시작된다. $lemma$ 홀수인 소수 $p$ 에 대하여 $p-1 = 2^s d$ 라고 할 때 gcd$(p,\;a) = 1$ 인 $a$ 에 대해서 $a^d \equiv 1$ (mod $p$) 또는 $0 \leq r < s$ 인 정수 $r$ 에 대하여 $a^{2^r d} \equiv.. 반복함수에서의 Cycle detection 유한집합 $X$ 에 대하여 $f : X\rightarrow X$ 인 함수 $f(x)$ 가 있다. $i>0$ 인 $i$ 에 대하여 $x_i = f(x_{i-1})$ 이라고 하면 수열 $x_i$ 는 반복되는 구간을 가짐이 자명하다. 그렇다면 반복의 시작점과 반복 주기는 어떻게 찾을 수 있을까? 이 글에서는 적은 공간복잡도로 빠른 시간 내에 답을 찾을 수 있는 알고리즘을 소개하려고 한다. Floyd's cycle-finding algorithm 우선 반복의 최초 시작점을 $\mu$, 가장 짧은 반복 주기를 $\lambda$ 라고 할 때 시간복잡도 $O(\mu+\lambda)$, 공간복잡도는 $O(1)$ 인 알고리즘이다. 이 알고리즘에서는 두개의 포인터를 사용하는데 두 포인터를 각각 $T$ 와 $H$ 라고 부르.. 이전 1 다음
