Участник:Pyatakovns/Ро-алгоритм Полларда

Автор: Пятаков Н.С. 419 группа

Свойства и структура алгоритмов

Общее описание алгоритма

Ро-алгоритм Полларда предназначен для решения задачи факторизации целых чисел. Этот метод был разработан Джоном Поллардом в 1975 г. Данный алгоритм основывается на следствиях из парадокса дней рождения и алгоритме Флойда поиска длины цикла в последовательности.

Математическое описание алгоритма

Пусть n – число, которое следует разложить. ρ-метод Полларда работает следующим образом:

1. Выбираем небольшое число [math]\displaystyle{ x_0 }[/math] и строим последовательность чисел [math]\displaystyle{ {x_n}, n = 0, 1, 2, ..., }[/math] определяя каждое следующее [math]\displaystyle{ x_{n+1} }[/math] по формуле [math]\displaystyle{ x_{n+1} =(x_{2n} −1)(modn) }[/math].