12.2.2 Метод Полларда

Схема этого метода (называемого -методом и широко используемого) заключается в следующем.     1. Выбрать функцию (обычно  -- многочлен степени не ниже 2).

    2. Случайно выбрать и, вычисляя по формуле , проверять тест этапа 3.

    3. Проверить условие для номеров , выбранных по одному из следующих правил:

     1) ;

     2) ;

     3) если , то .

Если делитель не найден, то переходим к следующим .

Метод Полларда имеет эвристическую оценку сложности .

Этим методом было разложено на множители число Ферма (см. [BP]). Сам метод впервые описан в [Poll75]; способ экономного использования памяти для хранения можно найти в [SSY].

В книге [Kob] приведено обоснование оценки сложности метода с использованием правила 3 выбора и .