Алгоритм Pollard’s rho

Алгоритм Pollard’s rho — это вероятностный алгоритм факторизации целых чисел, разработанный британским математиком Джоном Поллардом в 1975 году. Алгоритм предназначен для нахождения нетривиального делителя составного числа и относится к классу субэкспоненциальных методов факторизации. Своё название он получил из-за визуального сходства траектории последовательности, генерируемой алгоритмом, с греческой буквой ρ (ро) — сначала прямая линия, затем петля. Алгоритм эффективен для чисел, имеющих относительно небольшие простые делители (обычно до 10¹⁰), и широко применяется в криптоанализе, в частности, для взлома криптосистемы RSA при неудачном выборе параметров.

История

Джон Поллард представил алгоритм в 1975 году в статье «A Monte Carlo method for factorization» (метод Монте-Карло для факторизации). Идея алгоритма основана на парадоксе дней рождения и поиске коллизий в псевдослучайных последовательностях. В отличие от более ранних методов (например, пробного деления), алгоритм Полларда не требует перебора всех простых чисел до квадратного корня из числа, что делает его значительно быстрее для чисел с большими простыми множителями.

В 1980-х годах алгоритм был усовершенствован: были предложены различные варианты выбора псевдослучайной функции, а также методы ускорения вычислений с помощью алгоритма Флойда для обнаружения циклов. Несмотря на появление более мощных методов (например, квадратичного решета или решета числового поля), алгоритм Pollard’s rho остаётся популярным благодаря простоте реализации и низким требованиям к памяти.

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

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

Алгоритм Флойда для обнаружения циклов

Для обнаружения цикла в последовательности без хранения всех её элементов используется алгоритм Флойда (метод «черепахи и зайца»). Вводятся два указателя: медленный (черепаха) и быстрый (заяц). На каждом шаге медленный указатель вычисляет следующее значение последовательности один раз, а быстрый — два раза. Когда значения совпадают, это означает, что цикл обнаружен.

Шаги алгоритма

1. Выбирается начальное значение \( x_0 \) (обычно 2) и полиномиальная функция \( f(x) = x^2 + c \mod n \), где \( c \) — константа (часто 1).
2. Устанавливаются два указателя: \( a = x_0 \) (черепаха) и \( b = x_0 \) (заяц).
3. На каждом шаге:

• \( a = f(a) \)
• \( b = f(f(b)) \)
• Вычисляется \( d = \text{НОД}(|a - b|, n) \)

1. Если \( 1 < d < n \), то \( d \) — нетривиальный делитель \( n \). Алгоритм завершается.
2. Если \( d = n \), то алгоритм перезапускается с другим начальным значением или другой константой \( c \).
3. Если \( d = 1 \), шаги повторяются до обнаружения делителя или достижения предела итераций.

Математическое обоснование

Пусть \( p \) — простой делитель \( n \). Рассмотрим последовательность \( x_i \) по модулю \( p \). Поскольку возможных значений по модулю \( p \) всего \( p \), последовательность обязательно войдёт в цикл не более чем за \( p \) шагов (парадокс дней рождения). Ожидаемое количество шагов до обнаружения коллизии составляет \( O(\sqrt{p}) \). Таким образом, сложность алгоритма пропорциональна квадратному корню из наименьшего простого делителя \( p \).

Варианты и модификации

Выбор функции

Наиболее распространённая функция — \( f(x) = x^2 + 1 \mod n \). Однако при неудачном выборе (например, \( c = 0 \)) алгоритм может зациклиться или дать \( d = n \). В таких случаях выбирают другое начальное значение \( x_0 \) или другую константу \( c \).

Ускорение с помощью НОД

Вместо вычисления НОД на каждом шаге можно накапливать произведение разностей и вычислять НОД через каждые \( k \) шагов (например, 100). Это снижает затраты на вычисление НОД, но увеличивает риск пропуска делителя.

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

Существуют параллельные реализации алгоритма, в которых несколько потоков генерируют независимые последовательности и обмениваются значениями для обнаружения коллизий.

Применение

Криптоанализ RSA

Алгоритм Pollard’s rho используется для факторизации модуля RSA \( n = p \cdot q \), если один из простых множителей \( p \) или \( q \) относительно мал (например, менее \( 10^{10} \)). В современных криптосистемах RSA с ключами длиной 2048 бит и более такой сценарий маловероятен, но при неправильной генерации простых чисел (например, использование слабых генераторов случайных чисел) алгоритм может быть эффективен.

Тестирование на простоту

Хотя алгоритм не предназначен для доказательства простоты, его можно использовать для быстрого обнаружения составных чисел с малыми делителями. Если алгоритм не находит делитель за разумное время, число может быть простым (но это не гарантируется).

Факторизация в криптографии

Алгоритм применяется в составе более сложных методов факторизации, таких как метод квадратичного решета, для предварительного отсеивания чисел с малыми делителями.

Ограничения

• Алгоритм вероятностный: существует вероятность, что он не найдёт делитель за заданное число итераций, особенно если \( p \) велико.
• При \( p > 10^{10} \) алгоритм становится неэффективным по сравнению с другими методами.
• Алгоритм может дать тривиальный делитель \( n \) (само число \( n \)), что требует перезапуска с другими параметрами.
• Не подходит для факторизации чисел вида \( p^k \) (степень простого числа), так как в этом случае \( p \) будет найден, но неоднократно.

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

Пусть \( n = 8051 \). Выберем \( x_0 = 2 \), \( f(x) = x^2 + 1 \mod 8051 \).

• Шаг 1: \( a = 5 \), \( b = 26 \), \( d = \text{НОД}(21, 8051) = 1 \)
• Шаг 2: \( a = 26 \), \( b = 677 \), \( d = \text{НОД}(651, 8051) = 1 \)
• ...
• Шаг 10: \( a = 747 \), \( b = 2819 \), \( d = \text{НОД}(2072, 8051) = 97 \)

Таким образом, найден делитель 97. Второй делитель: \( 8051 / 97 = 83 \).

Сравнение с другими методами

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

• Алгоритм был вдохновлён методом Монте-Карло и парадоксом дней рождения: вероятность коллизии в последовательности из \( \sqrt{p} \) элементов превышает 50 %.
• Название «rho» (ро) предложил сам Поллард, заметив, что график последовательности напоминает греческую букву ρ: сначала прямая линия, затем петля.
• В 2023 году алгоритм использовался для факторизации 128-битных чисел в рамках соревнований по криптоанализу, показав время работы менее 1 секунды на современном процессоре.
• Алгоритм лёг в основу метода Pollard’s p-1, который эффективен для чисел, у которых один из делителей минус единица является гладким числом.

Источники

• 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.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). «Handbook of Applied Cryptography». CRC Press.
• Кнут, Д. Э. (2001). «Искусство программирования», том 2: Получисленные алгоритмы. — М.: Вильямс.