Принцип алгоритму:
Pollard Rho — це ймовірнісний алгоритм факторизації, особливо ефективний для знаходження середніх множників складених чисел. Назва походить від траєкторії, що нагадує грецьку літеру ρ (ро).
Стратегії оптимізації:
- Оптимізація пробним діленням:Спочатку використовуються малі прості числа (2, 3, 5, 7, 11...) для швидкого знаходження малих множників.
- Pollard Rho:Для великих складених чисел використовується псевдовипадкова послідовність x = (x² + c) mod n.
- Алгоритм виявлення циклу Флойда:Використання швидких та повільних вказівників для виявлення циклів, оптимізація просторової складності.
- Тест простоти Міллера-Рабіна:Після знаходження множника перевіряється, чи він простий, щоб уникнути непотрібної факторизації.
- Рекурсивна факторизація:Рекурсивна факторизація знайдених множників, поки всі не стануть простими.
Часова складність:
- Пробне ділення:O(√n), підходить для малих чисел або швидкого знаходження малих множників.
- Pollard Rho:Очікуваний час O(n^(1/4)), висока ефективність для чисел із середніми множниками.
- Міллера-Рабіна:O(k log³n), де k — кількість раундів тестування, використовується для перевірки простоти.