Математика / Арифметика и теория чисел

Метод Полларда rho: вероятностный поиск делителя

Метод Полларда rho ищет нетривиальный делитель составного числа, строя псевдослучайную последовательность по модулю n и вычисляя НОД разностей состояний с n. Совпадение по неизвестному простому множителю обнаруживает делитель раньше полного перебора.

Опубликовано: Обновлено:

Формула

$$x_{i+1}=x_i^2+c\pmod n,\quad y_{i+1}=f(f(y_i)),\quad d_i=\gcd(|x_i-y_i|,n)$$
Схема Трасса rho и извлечение делителя
f(x)=x²+c mod nx₀xygcd(|x−y|,n)1 — продолжить; 1<d<n — фактор; d=n — перезапуск

Разные скорости создают разность состояний; НОД этой разности с n извлекает общий простой множитель.

Обозначения

$n$
факторизуемое составное целое, число
$c$
константа функции итераций, остаток
$x_i,y_i$
черепаха и заяц на итерации i, остатки modulo n
$d_i$
кандидат в нетривиальный делитель, число
$f$
Итерационная функция (x² + c) mod n, —

Условия применения

Нужно составное нечётное n, функция f(x)=x²+c mod n и начальное x0. На каждой итерации считают x←f(x), y←f(f(y)), затем d=gcd(|x−y|,n). Если 1<d<n, найден делитель; d=1 означает продолжение, а d=n — неудачное столкновение и перезапуск с другим c или seed. Для чётного n сначала выносят множитель 2.

Ограничения

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

Подробное объяснение

Поллард rho использует различие между арифметикой по модулю n и арифметикой по модулю неизвестного простого делителя p. Последовательность x²+c выглядит псевдослучайной в кольце вычетов по модулю n. Если два состояния совпали по модулю p, то p делит x_i−y_i; вычисление gcd этой разности с n извлекает p, даже если сами состояния не совпали по модулю n.

Указатели «черепаха» и «заяц» идут с разной скоростью, как в обнаружении цикла. Но задача здесь не просто найти цикл: НОД разностей обнаруживает нетривиальный общий делитель разности и n. Пока d=1, разность не содержит доступного множителя; d=n означает, что полная разность кратна n, и нетривиальный множитель этим шагом не выделен.

На практике вместо одного НОД после каждой пары могут накапливать произведение нескольких разностей и делать пакетный НОД, но учебная версия с каждой итерацией прозрачнее. После получения d алгоритм запускают рекурсивно для d и n/d, проверяя простоту каждого результата. Случайная смена c или x0 меняет траекторию, а не математическое условие корректности найденного делителя.

Метод особенно полезен против чисел с небольшим множителем: ожидаемое число шагов связано с размером p примерно как квадратный корень из p в модели случайных состояний. Это эвристическая оценка, а не строгая гарантия каждой траектории. Для больших RSA-подобных полупростых чисел rho обычно недостаточен, и используют более мощные методы.

Нельзя принимать любое значение d за фактор. Если d=1, фактор не найден; если d=n, попытка провалилась; только 1<d<n даёт нетривиальное разложение. Простая проверка n mod d=0 и рекомбинация найденных множителей защищают от ошибок реализации.

Как пользоваться формулой

  1. Проверьте чётность и простоту n; для чётного числа сразу вынесите 2, а простое n не требует факторизации.
  2. Выберите c и x0, задайте f(x)=(x²+c) mod n, после чего установите x=y=x0 и d=1.
  3. На каждой итерации обновите x одним применением f, y двумя применениями f и вычислите d=gcd(|x−y|,n).
  4. Если d=1, продолжайте; если 1<d<n, проверьте делимость n на d и разделите задачу на d и n/d.
  5. Если d=n, остановите текущую трассу и перезапустите её с другой константой c или начальным значением.
  6. После рекурсии перемножьте простые множители и сравните произведение с исходным n, чтобы подтвердить полное разложение.

Историческая справка

Джон Поллард предложил rho-метод факторизации в 1975 году как вероятностный алгоритм, использующий обнаружение циклов и НОД. Название rho связано с греческой буквой ρ и формой поведения псевдослучайной последовательности: до цикла идёт хвост, затем повторяющийся участок. Идея опирается на парадокс дней рождения — в конечном поле две итерации становятся равными примерно после квадратного корня из числа возможных остатков.

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

Исторически rho не следует смешивать с p−1-методом Полларда: rho ищет столкновение последовательности, тогда как p−1 использует гладкость числа p−1. В современных библиотеках rho обычно является одним уровнем каскада факторизации рядом с пробным делением, тестами простоты и ECM. Его ценность — в простоте, малой памяти и хорошей практической скорости для небольших факторов.

Историческая линия формулы

Метод назван по Джону Полларду и его статье 1975 года о вероятностной факторизации. Варианты с ускоренным обнаружением циклов связаны с Ричардом Брентом, но базовая идея rho — итерации, столкновение и НОД — принадлежит работе Полларда.

Пример

Разложим n=91 при f(x)=x²+1 mod 91 и x0=y0=2. Шаг 1: x=5, y=f(5)=26, d=gcd(21,91)=7. Уже получен нетривиальный делитель 7, потому что 91=7·13. Проверка обязательна: 91 mod 7=0, а 1<7<91. Рекурсивное продолжение тривиально: 7 и 13 — простые, значит факторизация завершена. В этой короткой трассе столкновение по модулю 7 проявилось в первой разности, хотя x и y различны по модулю 91. Если бы на шаге вышло d=1, вычисление продолжалось бы; d=91 означало бы неудачный seed, а не доказательство простоты.

Частая ошибка

Частая ошибка — считать d=n найденным фактором: это означает неудачное столкновение и требует перезапуска. Нельзя пропускать проверку n mod d=0, особенно при переполнении или ошибке в модульном умножении. Скорости указателей должны различаться: обновление x и y одинаково не ищет цикл. Константу c выбирают в допустимом диапазоне, а отрицательную разность перед НОД заменяют модулем. Наконец, rho находит один делитель, но не гарантирует, что он прост; факторизацию продолжают рекурсивно.

Практика

Задачи с решением

Делитель числа 91

Условие. Для n=91, f(x)=x²+1 и x0=y0=2 выполните один шаг rho и найдите d.

Решение. x=5, y=f(f(2))=f(5)=26; |x−y|=21; gcd(21,91)=7. Проверка: 91=7·13.

Ответ. Найден делитель d=7.

Неудачная трасса

Условие. Что означает d=n=143 при попытке факторизовать 143 методом rho?

Решение. Найденная разность имеет с 143 весь общий модуль; это не нетривиальный делитель, потому что d не удовлетворяет 1<d<n. Меняют seed или c.

Ответ. Трассу перезапускают; фактор не найден.

Дополнительные источники

  • https://doi.org/10.1007/BF01933667
  • https://pages.cs.wisc.edu/~cs812-1/pollardrho.pdf
  • https://cacr.uwaterloo.ca/hac/about/chap3.pdf

Связанные формулы

Математика

Обратный элемент по модулю через расширенный алгоритм Евклида

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

Математика

Малая теорема Ферма: степени по простому модулю

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

Математика

Функция Эйлера: произведение по простым делителям

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

Математика

Быстрое возведение в степень по модулю двоичным методом

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.