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