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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Алгоритмы факторизации[править | править исходный текст]

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

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

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

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

Экспоненциальные алгоритмы[править | править исходный текст]

N - значение числа, n - кол-во цифр в числе.

Субэкспоненциальные алгоритмы[править | править исходный текст]

Решето числового поля[править | править исходный текст]

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

Применение в криптографии[править | править исходный текст]

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

Ссылки[править | править исходный текст]