알고리즘 원리:
Pollard Rho는 정수 소인수분해를 위한 확률적 알고리즘으로, 합성수에서 중간 크기의 인수를 찾는 데 특히 효과적입니다. 알고리즘 이름은 궤적이 그리스 문자 ρ(rho)와 비슷한 데서 유래했습니다.
최적화 전략:
- 시행 나눗셈 최적화:먼저 작은 소수(2, 3, 5, 7, 11...)로 시행 나눗셈을 수행하여 작은 인수를 빠르게 찾습니다.
- Pollard Rho:더 큰 합성수에 대해 의사난수 수열 x = (x² + c) mod n을 사용하여 인수를 찾습니다.
- Floyd의 순환 감지 알고리즘:빠른 포인터와 느린 포인터를 사용하여 수열의 순환을 감지하고 공간 복잡도를 최적화합니다.
- Miller-Rabin 소수 판별법:인수를 찾은 후 소수인지 확인하여 불필요한 추가 분해를 방지합니다.
- 재귀적 분해:찾은 인수를 모두 소수가 될 때까지 재귀적으로 분해합니다.
시간 복잡도:
- 시행 나눗셈:O(√n), 작은 숫자 또는 작은 인수를 빠르게 찾는 데 적합합니다.
- Pollard Rho:예상 시간 O(n^(1/4)), 중간 크기 인수를 가진 숫자에 매우 효율적입니다.
- Miller-Rabin:O(k log³n), k는 테스트 라운드 수, 소수 판별에 사용됩니다.