Метод Полларда — ро

Метод Полларда — ро (англ. Pollard's rho algorithm) — это вероятностный алгоритм факторизации целых чисел, разработанный британским математиком Джоном Поллардом в 1975 году. Алгоритм предназначен для нахождения нетривиального делителя составного числа и особенно эффективен для чисел с небольшими простыми множителями. Название метода происходит от греческой буквы «ро» (ρ), поскольку последовательность чисел, генерируемая алгоритмом, образует петлю, напоминающую по форме эту букву.

История

Метод был предложен Джоном Поллардом в статье «A Monte Carlo method for factorization», опубликованной в 1975 году в журнале BIT Numerical Mathematics. Поллард разработал алгоритм как альтернативу более медленным методам факторизации, таким как пробное деление, и вдохновлялся идеями из теории случайных чисел и парадокса дней рождения. В 1970-х годах алгоритм стал одним из первых практически применимых вероятностных методов факторизации, наряду с методом Ферма и методом квадратичного решета. Впоследствии метод Полларда — ро был усовершенствован, в частности, Ричардом Брентом в 1980 году, который предложил модификацию, сокращающую количество вычислений.

Принцип работы

Метод Полларда — ро основан на поиске коллизий в последовательности псевдослучайных чисел, генерируемых по модулю факторизуемого числа \(n\). Алгоритм использует функцию \(f(x) = (x^2 + c) \mod n\), где \(c\) — произвольная константа (обычно 1), для генерации последовательности \(x_1, x_2, x_3, \dots\). Из-за конечности множества остатков по модулю \(n\) последовательность неизбежно зацикливается, образуя цикл. Если простой делитель \(p\) числа \(n\) мал, то последовательность по модулю \(p\) зацикливается быстрее, чем по модулю \(n\), что позволяет обнаружить делитель через вычисление наибольшего общего делителя (НОД) разностей членов последовательности.

Алгоритм

Основная версия алгоритма включает следующие шаги:

1. Выбрать начальное значение \(x_0\) (например, 2) и константу \(c\) (например, 1).
2. Определить две последовательности: «медленную» \(x\) и «быструю» \(y\), где \(y\) обновляется дважды за шаг.
3. На каждом шаге вычислить \(x = f(x)\), \(y = f(f(y))\).
4. Вычислить \(d = \text{НОД}(|x - y|, n)\).
5. Если \(d = 1\), повторить шаги 3–4.
6. Если \(d = n\), алгоритм завершается неудачей (требуется смена параметров).
7. Если \(1 < d < n\), то \(d\) — нетривиальный делитель \(n\).

Алгоритм является вероятностным: его успех зависит от выбора начальных параметров и константы \(c\). При неудаче можно изменить \(c\) или \(x_0\) и повторить попытку.

Сложность и эффективность

Временная сложность метода Полларда — ро оценивается как \(O(n^{1/4})\) в среднем для случайных чисел, что значительно быстрее пробного деления, имеющего сложность \(O(n^{1/2})\). Однако точная оценка зависит от размера наименьшего простого делителя \(p\): алгоритм находит делитель за \(O(\sqrt{p})\) шагов. Для чисел с большими простыми множителями (например, произведения двух 100-значных простых чисел) метод может быть неэффективен, и применяются более мощные алгоритмы, такие как метод квадратичного решета или метод решета числового поля.

Модификации

Алгоритм Брента

В 1980 году Ричард Брент предложил модификацию, которая уменьшает количество вычислений НОД и ускоряет поиск коллизии. Вместо проверки на каждом шаге Брент рекомендует проверять НОД только после каждого \(2^k\)-го шага, что снижает вычислительную нагрузку. Эта версия широко используется в современных реализациях.

Параллельная версия

Метод Полларда — ро может быть распараллелен для использования на нескольких процессорах. Однако из-за вероятностной природы алгоритма параллелизация не даёт линейного ускорения, так как каждый поток генерирует независимую последовательность, и делитель может быть найден любым из них.

Применение

Метод Полларда — ро применяется в криптографии для проверки стойкости ключей, основанных на больших простых числах, например, в алгоритмах RSA и Диффи — Хеллмана. Он также используется в математических пакетах (например, PARI/GP, Maple, Mathematica) и библиотеках для факторизации (GMP-ECM). В сочетании с другими методами, такими как метод эллиптических кривых (ECM) и метод квадратичного решета, алгоритм Полларда — ро является частью стандартных процедур факторизации в системах компьютерной алгебры.

Пример работы

Для числа \(n = 8051\) (произведение 83 и 97) алгоритм с \(x_0 = 2\) и \(c = 1\) может найти делитель 83 за несколько шагов. Последовательность по модулю 83 зацикливается быстрее, чем по модулю 8051, что приводит к коллизии и вычислению НОД.

Критика и ограничения

Основным недостатком метода является его вероятностный характер: при неудачном выборе параметров алгоритм может не найти делитель или работать слишком долго. Для чисел, являющихся точными квадратами или степенями простых чисел, метод может давать сбои. Кроме того, алгоритм не гарантирует нахождение всех делителей — он находит только один нетривиальный делитель за запуск. Для полной факторизации требуется повторное применение к полученным множителям.

Интересные факты

• Название «ро» связано с тем, что график последовательности чисел напоминает букву ρ: хвост (начальная часть) и петля (цикл).
• Метод Полларда — ро был одним из первых алгоритмов, использующих идею «парадокса дней рождения» для ускорения вычислений.
• В 1990-х годах алгоритм применялся для факторизации чисел длиной до 50 десятичных знаков; с ростом вычислительных мощностей его эффективность снизилась для больших чисел.

Источники

• Pollard, J. M. (1975). «A Monte Carlo method for factorization». BIT Numerical Mathematics, 15(3), 331–334.
• Brent, R. P. (1980). «An improved Monte Carlo factorization algorithm». BIT Numerical Mathematics, 20(2), 176–184.
• Кнут, Д. Э. (1998). «Искусство программирования». Том 2: Получисленные алгоритмы. — М.: Вильямс.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.