Математика / Арифметика и теория чисел
Метод Полларда rho: вероятностный поиск делителя
Метод Полларда rho ищет нетривиальный делитель составного числа, строя псевдослучайную последовательность по модулю n и вычисляя НОД разностей состояний с 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 и рекомбинация найденных множителей защищают от ошибок реализации.
Как пользоваться формулой
- Проверьте чётность и простоту n; для чётного числа сразу вынесите 2, а простое n не требует факторизации.
- Выберите c и x0, задайте f(x)=(x²+c) mod n, после чего установите x=y=x0 и d=1.
- На каждой итерации обновите x одним применением f, y двумя применениями f и вычислите d=gcd(|x−y|,n).
- Если d=1, продолжайте; если 1<d<n, проверьте делимость n на d и разделите задачу на d и n/d.
- Если d=n, остановите текущую трассу и перезапустите её с другой константой c или начальным значением.
- После рекурсии перемножьте простые множители и сравните произведение с исходным 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
Связанные формулы
Математика
Обратный элемент по модулю через расширенный алгоритм Евклида
Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Математика
Малая теорема Ферма: степени по простому модулю
Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.
Математика
Функция Эйлера: произведение по простым делителям
Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.
Математика
Быстрое возведение в степень по модулю двоичным методом
Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.