12.3.5 Другие методы

Для факторизации целых чисел существует также -метод Полларда. Недавно он усовершенствован в работе [MonS]. В нем отсутствуют какие-либо оценки сложности, однако из идей этого метода возник метод факторизации с помощью эллиптических кривых, который имеет наилучшую оценку сложности среди субэкспоненциальных алгоритмов. Описание метода см. в [Len87], [Mont], [Kob]. Эвристическая оценка сложности составляет арифметических операций, где  -- наименьший простой делитель . Если вспомнить, что , то получим оценку сложности . Метод запрограммирован и широко применяется.