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

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

Пусть надо разложить на множители число P

• Шаг 1. Выбирается многочлен с целочисленными коэффициентами, степени не выше 2. Обычно берется многочлен вида (mod P).
• Шаг 2. Случайно выбирается меньше .
• Шаг 3. Вычисляются значения .
• Шаг 4. Находится .
• Шаг 5. Если , происходит переход на шаг 3, если , происходит остановка — факторизацию провести не удалось. Если , то найдено разложение числа P.

Альтернативное описание

• Шаг 1. Выбирается многочлен с целочисленными коэффициентами, степени не выше 2 и целое число m.
• Шаг 2. Случайно выбирается меньше .
• Шаг 3. Вычисляются значения .
• Шаг 4. Для полагаем и для каждого вычисляем . Если , то нетривиальный делитель числа n найден. Если d=1 или d=P, то переходим к следующему значению h.

Сложность алгоритма

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