ро-метод Полларда

ρ-aлгоритм Джона Полларда, предложенный им в 1975 году, служит для факторизации целых чисел. Он основан на том, что вычисляется некий многочлен степени не выше второй от начального числа Х — f(X).
[править]
Описание алгоритма

Пусть надо разложить на множители число P
Шаг 1. Выбирается многочлен f(x) с целочисленными коэффициентами, степени не выше 2. Обычно берется многочлен вида y = x2 + c(mod P).
Шаг 2. Случайно выбирается x0 = y0 меньше P.
Шаг 3. Вычисляются значения xi = f(xi − 1)(modP),yi = f(f(yi − 1))(modP).
Шаг 4. Находится d = ( | xi − yi | ,P).
Шаг 5. Если d = 1, происходит переход на шаг 3, если d = P, происходит остановка - факторизацию провести не удалось. Если 1 < d < P, то найдено разложение числа P.


[править]
Альтернативное описание
Шаг 1. Выбирается многочлен f(x) с целочисленными коэффициентами, степени не выше 2 и целое число m.
Шаг 2. Случайно выбирается x0 меньше P.
Шаг 3. Вычисляются значения xi = f(xi − 1)(modP).
Шаг 4. Для h = 0,1,...,[logm] полагаем j = 2h − 1 и для каждого 2h < = k < 2h + 1 вычисляем d = ( | xj − xk | ,P). Если 1 < d < P, то нетривиальный делитель числа n найден. Если d=1 или d=P, то переходим к следующему значению h.
[править]
Сложность алгоритма

Пусть n — составное число. Тогда существует такая константа C, что для любого положительного числа λ вероятность события, состоящего в том, что ρ-метод Полларда не найдет нетривиального делителя n за время , не превосходит величины e − λ