Pollard Rho 는 큰 정수 N 의 비자명 약수를 O(N^(1/4)) 확률적 시간에 찾는 알고리즘. 생일 역설 (Birthday Paradox) 을 활용해 난수 수열의 충돌로 GCD 를 계산. Miller-Rabin 과 함께 사용해 N ≤ 10^18 수준의 소인수분해를 완전히 해결.
문제 상황과 동기
N (10^12 ~ 10^18) 의 소인수를 모두 찾아라.
시행 나눗셈: O(√N). N=10^18 이면 10^9 회, 너무 큼.
SPF 전처리: O(N) 전처리 필요. N=10^18 은 메모리 초과.
Pollard Rho: O(N^(1/4)). N=10^18 이면 약 31623 회 반복으로 충분.
핵심 통찰: 1..N-1 에서 무작위 두 수를 뽑아 차이가 N 과 공약수를 가질 확률은 생각보다 높다 (생일 역설). f(x) = x^2 + c 로 생성한 수열은 마치 ρ (rho) 모양을 그리며 사이클 형성.
시각화
핵심 아이디어
난수 수열 x_{i+1} = f(x_i) = (x_i^2 + c) mod N.이 수열은 유한하므로 언젠가 사이클에 진입 (ρ 형태).Floyd 의 토끼와 거북이로 사이클 감지:x = 2, y = 2while true: x = f(x) y = f(f(y)) d = gcd(|x - y|, N) if 1 < d < N: return d # 비자명 약수 발견 if d == N: retry with new c발견한 d 와 N/d 를 재귀적으로 분해.
알고리즘
pollard_rho(N): if N % 2 == 0: return 2 if is_prime(N): return N c = 1 while true: x = y = 2 f(t) = (t * t + c) % N d = 1 while d == 1: x = f(x) y = f(f(y)) d = gcd(|x - y|, N) if d != N: return d c += 1 # 다른 c 로 재시도factorize(N): if N == 1: return p = pollard_rho(N) factorize(p) factorize(N / p)
구현
// Pollard Rho + Miller-Rabin. N < 2^64#include <bits/stdc++.h>using namespace std;using ll = long long;using u128 = __uint128_t;ll mulmod(ll a, ll b, ll m) { return (u128)a * b % m;}ll powmod(ll a, ll b, ll m) { ll res = 1 % m; while (b > 0) { if (b & 1) res = mulmod(res, a, m); a = mulmod(a, a, m); b >>= 1; } return res;}bool witness(ll n, ll a) { if (n % a == 0) return n == a; ll d = n - 1, s = 0; while (d % 2 == 0) { d /= 2; s++; } ll x = powmod(a, d, n); if (x == 1 || x == n - 1) return true; for (int i = 1; i < s; i++) { x = mulmod(x, x, n); if (x == n - 1) return true; if (x == 1) return false; } return false;}bool is_prime(ll n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) if (!witness(n, a)) return false; return true;}ll pollard_rho(ll n) { if (n % 2 == 0) return 2; if (is_prime(n)) return n; ll x, y, d, c = 1; auto f = [n, &c](ll v) { return (mulmod(v, v, n) + c) % n; }; while (true) { x = y = 2; d = 1; while (d == 1) { x = f(x); y = f(f(y)); d = gcd(abs((long long)(x - y)), n); } if (d != n) return d; c++; }}vector<ll> factors;void factorize(ll n) { if (n == 1) return; if (is_prime(n)) { factors.push_back(n); return; } ll p = pollard_rho(n); factorize(p); factorize(n / p);}int main() { ll n; cin >> n; factorize(n); sort(factors.begin(), factors.end()); for (ll p : factors) cout << p << " "; cout << "\n";}
# Pollard Rho + Miller-Rabinimport math, sys, randomdef miller_rabin(n, a): if n % a == 0: return n == a d, s = n - 1, 0 while d % 2 == 0: d //= 2; s += 1 x = pow(a, d, n) if x == 1 or x == n - 1: return True for _ in range(s - 1): x = pow(x, 2, n) if x == n - 1: return True if x == 1: return False return Falsedef is_prime(n): if n < 2: return False if n == 2: return True if n % 2 == 0: return False for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]: if a >= n: continue if not miller_rabin(n, a): return False return Truedef pollard_rho(n): if n % 2 == 0: return 2 if is_prime(n): return n c = 1 while True: x = y = 2 f = lambda v: (v * v + c) % n d = 1 while d == 1: x = f(x) y = f(f(y)) d = math.gcd(abs(x - y), n) if d != n: return d c += 1def factorize(n, res): if n == 1: return if is_prime(n): res.append(n); return p = pollard_rho(n) factorize(p, res) factorize(n // p, res)n = int(sys.stdin.readline())factors = []factorize(n, factors)factors.sort()print(" ".join(map(str, factors)))
stdin
123456789
결과
3 3 3607 3803
stdin
1000000007
결과
1000000007
복잡도
항목
값
시간 (평균)
O(N^(1/4))
시간 (최악)
O(N^(1/2)) (드문 경우)
공간
O(log N) (재귀 스택)
Miller-Rabin 포함
O(N^(1/4) log^3 N)
c 값이 사이클 감지에 실패하면 재시도 필요. 평균적으로 1~3 회면 성공.
변형
변형
설명
Brent 의 개선
Floyd 대신 Brent 의 사이클 감지. 30~50% 빠름
Pollard p-1
p-1 이 smooth 한 소인수 특화
Quadratic Sieve (QS)
O(exp(√(log N log log N))). 100자리 이상
Number Field Sieve (NFS)
RSA 크기 (200자리+) 공략
함정
1. f(x) = x^2 + c 의 선택
보통 c=1 시작. 실패하면 c=2, 3, … 증가. c = random.randint(1, n-1) 도 자주 사용.
2. 무한 루프 방지
d == n 이면 현재 c 에서 실패. c 를 바꾸고 재시도.
3. is_prime 체크 필수
pollard_rho 에 소수 N 이 들어오면 무한 루프. 진입 전 is_prime(N) 호출 필수.
💬 댓글