Метод факторизации Полларда

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

История

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

Основная идея алгоритма

Алгоритм основан на следующем наблюдении: если \( p \) — некоторый простой делитель числа \( N \), то для случайной последовательности чисел \( x_1, x_2, \dots \) по модулю \( p \) ожидается, что коллизия (повтор значения) произойдет после примерно \( \sqrt{p} \) шагов (парадокс дней рождения). Поллард предложил генерировать последовательность чисел по модулю \( N \) с помощью рекуррентной функции, например:

\[ x_{i+1} = (x_i^2 + c) \mod N, \]

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

Алгоритм

Классический вариант (Флойда)

1. Выбрать начальное значение \( x_0 \) (например, 2) и константу \( c \) (например, 1).
2. Определить две переменные: \( a = x_0 \) и \( b = x_0 \).
3. Итеративно обновлять:

• \( a = f(a) \mod N \)
• \( b = f(f(b)) \mod N \) (двойной шаг).

1. На каждом шаге вычислять \( d = \text{НОД}(|a - b|, N) \).
2. Если \( 1 < d < N \), то \( d \) — нетривиальный делитель \( N \). Алгоритм завершается.
3. Если \( d = N \), то алгоритм не сработал для данной константы \( c \); следует изменить \( c \) или \( x_0 \) и повторить.
4. Если \( d = 1 \), продолжить итерации до достижения предела (например, \( \sqrt[4]{N} \) шагов).

Вариант Брента

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

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

Ожидаемое время работы алгоритма составляет \( O(\sqrt{p}) \) операций по модулю \( N \), где \( p \) — наименьший простой делитель \( N \). В худшем случае, когда \( N \) — произведение двух простых чисел одинакового размера, сложность составляет \( O(N^{1/4}) \) операций. Для чисел с малыми делителями (например, до \( 10^6 \)) алгоритм работает чрезвычайно быстро — за доли секунды. Однако для чисел с большими простыми делителями (например, RSA-модулей) он становится непрактичным.

Применение

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

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

Рассмотрим факторизацию числа \( N = 8051 \). Выберем \( x_0 = 2 \), \( c = 1 \). Последовательность:

• \( x_1 = (2^2 + 1) \mod 8051 = 5 \)
• \( x_2 = (5^2 + 1) \mod 8051 = 26 \)
• \( x_3 = (26^2 + 1) \mod 8051 = 677 \)
• \( x_4 = (677^2 + 1) \mod 8051 = 7474 \)
• \( x_5 = (7474^2 + 1) \mod 8051 = 2839 \)
• ...

Параллельно вычисляем \( b \) с двойным шагом: \( b_0 = 2 \), \( b_1 = 5 \), \( b_2 = 26 \), \( b_3 = 677 \), \( b_4 = 7474 \), \( b_5 = 2839 \). На шаге 5: \( |a - b| = |2839 - 2839| = 0 \), НОД(0, 8051) = 8051 — коллизия по модулю \( N \), алгоритм не сработал. Меняем \( c = 2 \) и повторяем, что в итоге даёт делитель 97.

Ограничения и недостатки

• Вероятностный характер: алгоритм может не найти делитель за разумное время, если константа \( c \) неудачна. Требуется несколько попыток с разными параметрами.
• Неприменимость для чисел с большими простыми делителями: если \( N \) — произведение двух простых чисел порядка \( 10^{100} \), алгоритм практически неэффективен.
• Зависимость от выбора функции: функция \( f(x) = x^2 + c \) может порождать короткие циклы, что приводит к преждевременной коллизии по модулю \( N \).
• Не подходит для факторизации чисел вида \( p^k \): алгоритм может не обнаружить делитель, если \( N \) — степень простого числа.

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

• Пробное деление: эффективно для малых делителей (до \( 10^6 \)), но экспоненциально замедляется для больших.
• Метод Ферма: эффективен для чисел, близких к квадрату, но неэффективен для чисел с большими разностями между множителями.
• Метод эллиптических кривых (ECM): более мощный, но сложнее в реализации; используется для чисел с делителями до \( 10^{30} \).
• Метод квадратичного решета (QS): детерминированный, эффективен для чисел до \( 10^{100} \), но требует больше памяти.

Реализация

Алгоритм легко реализуется на большинстве языков программирования. Пример на Python (классический вариант Флойда):

```python import math

def pollard_rho(n, c=1): if n % 2 == 0: return 2 x = 2 y = 2 d = 1 while d == 1: x = (x x + c) % n y = (y y + c) % n y = (y * y + c) % n d = math.gcd(abs(x - y), n) if d == n: return None # Попробовать другую константу return d ```

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

• Алгоритм назван «ρ-алгоритмом» из-за формы графа последовательности, которая напоминает греческую букву ρ (ро): сначала последовательность движется случайно, затем входит в цикл.
• Поллард также разработал метод дискретного логарифмирования, известный как ρ-алгоритм Полларда для дискретного логарифма.
• В 2020-х годах алгоритм остаётся одним из самых простых для понимания и реализации методов факторизации, используемых в учебных целях.

Источники

• Pollard, J. M. (1975). «A Monte Carlo method for factorization». BIT Numerical Mathematics.
• Brent, R. P. (1980). «An improved Monte Carlo factorization algorithm». BIT Numerical Mathematics.
• Кнут, Д. Э. (1998). «Искусство программирования», том 2: Получисленные алгоритмы.
• Василенко, О. Н. (2003). «Теоретико-числовые алгоритмы в криптографии».