Pollard's Rho

어떤 수의 인수(factor)를 찾아내는 알고리즘이다.
특히 큰 수의 인수를 찾을 때 유용하고, 메모리를 거의 차지하지 않으며 O(n^(1/4))의 시간복잡도를 보인다고 한다.

gcd 와 x^2+-a (1,-1) 을 이용하는데, 정확한 수학적 원리는 모르겠다.
실제 테스트를 해봤는데, 약수를 전부 찾아내는건 아니지만 큰 수인데 인수가 2~3개 밖에 안되는 경우도 빠르게 찾아냈다.

참고

소스