Факторизация целых чисел

Факториза́цией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

• Варновский Н. П. Проблема P =? NP, классы сложностей и криптография, 2005.
• Д. Кнут Раздел 4.5.4. Разложение на простые множители // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — С. 425—468. — 832 с. — ISBN 0-201-89684-2
• Ю. И. Манин, А. А. Панчишкин. I.2.3. Разложение больших чисел на множители // Введение в теорию чисел. — М.: ВИНИТИ, 1990. — Т. 49. — С. 72—106. — 341 с. — (Итоги науки и техники. Серия «Современные проблемы математики. Фундаментальные направления».).
• Ю. В. Нестеренко. Глава 4.7. Как раскладывают составные числа на множители // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 15 мая 2011.