폴라드 로 알고리즘은 $O(n^\frac{1}{4})$ 시간에 동작하는 무작위 정수 소인수분해 알고리즘으로, 생일 역설의 다음 따름정리에 기반합니다:
어떤 두 수가 일치하려면 멀티셋에 1부터 $n$까지의 무작위 수를 $O(\sqrt{n})$개 추가해야 합니다.
#폴라드의 $\rho$ 알고리즘
그러면 수 $n$을 소인수분해하고자 합니다. $n = p q$이고 $p \approx q$라고 가정합시다. 아마도 이보다 더 어려운 경우는 없다는 것이 분명합니다. 이 알고리즘은 가장 작은 약수를 반복적으로 찾아내어, 문제를 적어도 절반 이하 크기의 문제로 줄입니다.
다음 함수를 살펴봅시다:
$$ f(x) = (x+1)^2 \bmod n $$알고리즘에서 필요한 성질 중 하나는 이 함수가 정수론의 관점에서 «충분히 무작위적»이라는 것입니다. 이 함수에 대해서는 나중에 다시 다루겠습니다.
정의. 각 정점에서 나가는 간선이 $x \to f(x)$ 하나뿐인 그래프를 함수 그래프라고 합니다.
함수 그래프에서 임의의 원소의 «궤적»을 그려 보면, 어떤 경로가 이어지다가 사이클로 바뀌는 모양이 됩니다.
어떤 원소 $x_0$의 궤적 {$x_0$, $f(x_0)$, $f(f(x_0))$, $\ldots$}을 생각해 봅시다. 여기서 각 원소를 $n$의 소인수 중 더 작은 것인 $p$로 나눈 나머지를 머릿속으로 취하여 새로운 수열을 만들어 봅시다.
명제. 이 수열에서 사이클의 기대 길이는 $O(\sqrt[4]{n})$입니다.
증명: $p$가 더 작은 약수이므로 $p \leq \sqrt n$입니다. 이제 생일 역설의 따름정리에 그대로 대입해 봅시다. 어떤 두 원소가 일치하려면 집합에 $O(\sqrt{p}) = O(\sqrt[4]{n})$개의 원소를 추가해야 하며, 이는 곧 수열에 사이클이 생긴다는 뜻입니다.
이러한 수열에서 사이클을 찾는다면, 즉 다음을 만족하는 $i$와 $j$를 찾는다면
$$ f^i(x_0) \equiv f^j(x_0) \pmod p $$ 그러면 $n$의 어떤 약수도 찾을 수 있으며, 그 약수는 다음과 같습니다. $$ d = \gcd(|f^i(x_0) - f^j(x_0)|, n) $$이 수는 $n$보다 작고 $p$로 나누어떨어지므로, 그것과 같아야 합니다.
이 알고리즘은 본질적으로 표준적인 “거북이와 토끼” 알고리즘을 사용하여 이 수열에서 사이클을 찾습니다. 서로 멀어지는 두 포인터 $j$와 $i = 2j$를 유지하면서 $f^i(x_0) \equiv f^j(x_0)$인지 확인하는데, 이는 다음을 확인하는 것과 동치입니다.
$$ \gcd(|f^i(x_0) - f^j(x_0)|, n) \not \in \{ 1, n \} $$간단하지만 가장 신뢰할 만하지는 않은 구현은 다음과 같습니다:
typedef long long ll;
inline ll f(ll x, ll n) { return (__int128_t) (x + 1) * (x + 1) % n; }
ll find_divisor(ll n, ll seed = 1) {
ll x = seed, y = seed;
ll d = 1;
while (d == 1 || d == n) {
// двигаем первый указатель на шаг
y = f(y);
// а второй -- на два
x = f(f(x));
// пытаемся найти общий делитель
d = gcd(abs(x - y), n);
}
return d;
}
알고리즘이 무작위화되어 있으므로, 완전한 구현에서는 여러 세부 사항을 고려해야 합니다. 예를 들어, 때로는 약수를 찾지 못한다는 점(여러 번 실행해야 합니다)이나, 소수를 소인수분해하려고 하면 $O(\sqrt n)$에 동작한다는 점(소수 판별이나 시간 제한에 의한 중단을 추가해야 합니다)이 있습니다.
이 구현의 점근적 복잡도는 $O(\sqrt[4]{n} \log n)$입니다. 매 반복마다 $\gcd$를 $O(\log n)$에 구하기 때문입니다. 다음과 같은 기법으로 로그를 없앨 수 있습니다. 상수 $M = \Theta(\log n)$을 정하고, $M$번의 연속된 반복 동안 값들의 곱 $P = \prod |f^i(x_0) - f^j(x_0)|$를 $n$으로 나눈 나머지로 유지합니다. 그리고 매 단계마다 $\gcd$를 계산하여 확인하는 대신, $M$번의 반복마다 $\gcd(P, n)$을 계산합니다.
약수에 도달하면 그 약수는 곱에 반영되며, 최대 $M = \Theta(\log n)$ 단계 안에 곱의 $\gcd$에서 그 약수를 찾게 됩니다. 이제 $\Theta(\log n)$번마다 한 번씩만 $\gcd$를 $O(\log n)$에 계산하므로, 점근적 복잡도에서 로그 인자가 사라집니다.
#참고 사항
큰 수의 소인수분해는 암호학의 맥락에서 흥미롭습니다. 예를 들어 RSA 알고리즘은 선형 시간 안에 소인수분해를 할 수 없다는 가정에 기반합니다.
또한 준지수 시간이지만 다항 시간은 아닌 소인수분해 알고리즘도 존재합니다. 인류는 $10^{250}$ 정도 크기의 수를 소인수분해할 수 있습니다.
쇼어 알고리즘을 사용하면 양자 컴퓨터에서 수를 다항 시간에 소인수분해할 수 있습니다. 그러나 2019년 기준으로 모든 양자 계산은 일반 컴퓨터에서 시뮬레이션하는 편이 더 쉽습니다. 실제 양자 컴퓨터에서 소인수분해된 가장 큰 수는 4088459입니다.