Разложение на множители

Факториза́ция — разложение данного натурального числа на простые множители.

В отличие от задачи распознавания простоты числа, факторизация предположительно является сложной задачей.

Алгоритмы факторизации

В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа — экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих праметров (то есть от длины самого числа в бинарном представлении). Вторая группа — субэкспоненциальные алгоритмы, для обозначения сложности которых принята L-нотация:

$L_{N}(\alpha,\;c):=O(\exp((c+o(1))(\log N)^{\alpha}(\log\log N)^{1-\alpha})),$

где N — число подлежащее факторизации, 0 < α < 1 и c — некоторые константы.

Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора.

Экспоненциальные алгоритмы

• Перебор возможных делителей — наиболее тривиальный алгоритмом факторизации с вычислительной сложность Θ(N^{1 / 2}).
• ρ-алгоритм Полларда имеет сложность Θ(N^{1 / 4});
• p-1 алгоритм Полларда;
• p+1 алгоритм Вильямса;
• метод квадратичных форм Шенкса имеет сложность O(N^{1 / 4});
• метод Шермана — Лемана.

Субэкспоненциальные алгоритмы

• метод непрерывных дробей имеет сложность $L_N(1/2,\;\sqrt{2})$;
• метод квадратичного решета имеет сложность $L_N(1/2,\;1)$;
• метод эллиптических кривых имеет сложность $L_p(1/2,\;\sqrt{2})$, где p — наименьшее простое, которое делит N.

Решето числового поля

В настоящее время самыми эффективными алгоритмами факторизации являются вариации решета числового поля:

• общий метод решета числового поля со сложностью $L_N(1/3,\;(64/9)^{\frac{1}{3}})$;
• специальный метод решета числового поля со сложностью $L_N(1/3,\;(32/9)^{\frac{1}{3}})$. Однако для использования этого алгоритма накладываются определённые условия на число, подлежащее факторизации.

Применение в криптографии

Предполагаемая сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как

Ссылки

• Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография. 2005.
• Онлайновые программы для факторизации чисел: [1], [2], [3]
• Дональд Э. Кнут. Искусство программирования. Т.2 Получисленные алгоритмы. - Вильямс, 2007, - Раздел 4.5.4. Разложение на простые множитеели. с. 425-468