Принцип на алгоритъма:
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 е броят тестове, за проверка за простота.