Эта статья является кандидатом в добротные статьи

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Схематическая иллюстрация факторизации числа 525.

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

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

Предположение о том, что для больших чисел задача факторизации является вычислительно сложной лежит в основе широко используемых алгоритмов (например, RSA). Множество областей математики и информатики находят применение в решении этой задачи. Среди них: эллиптические кривые, алгебраическая теория чисел и квантовые вычисления.

История[править | править вики-текст]

Задача поиска эффективных способов разложения целых чисел на множители интересовала математиков с давних времен, особенно специалистов в области теории чисел. Существуют предположения о том, что один из первых методов разложения, заключающихся в том, чтобы представить число в виде разности квадратов n = x^2 - y^2, а затем, вычисляя \gcd(n, x-y), попытаться найти нетривиальный делитель n, был предложен Ферма. Данный способ позволяет находить два мало отличающихся по величине делителя  числа быстрее, чем простой перебор делителей[1].

Создание алгоритма RSA стимулировало бурные исследования в области факторизации целых чисел.

Далее Лежандром было обнаружено, что при таком подходе достаточно получить сравнение x^2 \equiv y^2 \mod n и использовал для этого цепные дроби. Также Эйлером и Гауссом были предложены некоторые способы нахождения чисел, связанных этим сравнением[1].

Одним из ключевых моментов в развитии факторизации целых чисел было создание алгоритма RSA, что возобновило интерес ученых в данном направлении, так как имело практическое применение в области шифрования. Этот алгоритм был предложен в 1977 году тремя учеными Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского Технологического Института и  назван по первым буквам фамилий авторов методом RSA. Он основан на идее криптографии с открытым ключом и для взлома системы необходимо выполнить разложение числа на простые сомножители. На момент публикации алгоритма RSA были известны методы, которые позволяли факторизовать числа, состоящие не более чем из 25—30 цифр, а наиболее известным и применяемым все еще оставался метод Ферма. Метод RSA позволяет факторизовывать числа из 100 и более десятичных знаков. Создатели в свою очередь пообещали символические 100 долларов США, за факторизацию числа из 129 десятичных знаков[2].

На популярность задачи факторизации также повлияла публикация в 1977 году в журнале Scientific American Мартина Гарднер «Новый алгоритм шифрования, для взлома которого потребуется миллионы лет». Столь громкое название было восприняно в качестве вызова всему математическому сообществу. В результате этой гонки было предложено несколько  новых и нестандартных идей факторизации[2].

Эпопея с разложением 129-значного числа завершилась в 1994 году, когда коллектив под руководством А. Ленстры, используя 1600 компьютеров в течение 220 дней, подгтовили систему линейных уравнений, содержащую более полумиллиона неизвестных, котрая в дальнейшем была решена суперкомпьютером за 2 дня. Несмотря на то, что в то время уже были известны методы решета числового поля, данный результат был получен с помощью алгоритма квадратичного решета[2].

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

Как правило, на вход таких алгоритмов подается число n \in \N, которое необходимо факторизовать, состоящее из N = [\log_2 n] + 1 символов (если n представлено в двоичном виде)[3]. При этом алгоритм ищет первый простой делитель, после чего, при необходимости, можно запустить алгоритм заново для дальнейшей факторизации. Так же, прежде чем начинать факторизацию большого числа следует убедиться в том, что оно не просто. Для этого достаточно пройти тест числа на простоту. Эта задача детерменированно разрешима за полиномиальное время[4].

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

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

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

Перебор возможных делителей[править | править вики-текст]

Сложность  O(\sqrt{n}\log^2 n) или  O(\sqrt{n}\log n) .

Один из самых простых и очевидных алгоритмов факторизации, заключающийся в том, чтобы последовательно делить факторизуемое число n на натуральные числа от 1 до \lceil \sqrt{n} \rceil. Формально достаточно делить только на простые числа в этом интервале, однако, для этого необходимо знать их множество. На практике составляется таблица простых чисел и производится проверка небольших чисел(например, до 2^{16}). Для очень больших чисел алгоритм не используется в силу низкой скорости работы[6].

Метод факторизации Ферма[править | править вики-текст]

Сложность  O(n) или O(exp(N)).

Идея алгоритма заключается в поиске таких чисел A и B, что факторизуемое число n представимо в виде: n = A^2 - B^2 = (A-B)(A+B). Как и метод пробного деления, обычно не применяется на практике для факторизации больших чисел, так как имеет экспоненциальную сложность. Метод примечателен тем, что реализуем без операции деления, а только лишь с операциями сложения и вычитания[8]. Следует так же отметить, что если n = pq, при условии того, что p и q — простые числа не сильно отличающиеся по величине, то метод Ферма факторизует n достаточно быстро[9].

ρ-алгоритм Полларда[править | править вики-текст]

Сложность O(n^{1/4}).

Алгоритм Полларда является вероятностным алгоритмом, позволяющим находить делитель составного числа n, работающим со сложностью, зависящей лишь от величины делителя, но не величины факторизуемого числа n. Это обуславливает удобство применимости данного алгоритма в тех случаях, когда другие алгоритмы, сложность которых зависит от n, становятся неэффективны[11]. Примечателен так же тем, что существует вариант реализации такого алгоритма, при котором достаточно в памяти храниить всего 3 целых числа[12].

Алгоритм Ленстры[править | править вики-текст]

Сложность O(n^{1/3}\log^2n).

Следует отметить, что несмотря на относительно неплохую эффективность среди экспоненциальных алгоритмов, в алгоритме Ленстры есть необходимость неоднократно вычислять квадратный корень в одном из шагов алгоритма, что, безусловно, является более трудоемким, чем сложение или вычитание[14].

Алгоритм Полларда — Штрассена[править | править вики-текст]

Сложность O(n^{1/4}\log^4n).

Данный алгоритм имеет наилучшую оценку сложности среди детерминированных алгоритмов факторизации. Он может использоваться непосредственно для факторизации не очень больших целых чисел, а так же в качестве вспомогательного алгоритма в субэкспоненциальном методе Диксона[16].

P-1 алгоритм Полларда[править | править вики-текст]

Сложность O(n^{1/2}\log^cn)[17].

Несмотря на экспоненциальную оценку сложности, алгоритм во всех случаях быстро находит небольшие простые делители n, потому что они являются степенно-гладкими для небольшой границы гладкости B. В практических задачах данный алгоритм обычно используется до применения субэкспоненциальных алгоритмов факторизации, чтобы отделить небольшие простые делители числа n[17].

Метод Лемана[править | править вики-текст]

Cложность O(n^{1/3}).

В настоящее время алгоритм представляет скорее исторический, чем практический интерес, так как этот алгоритм был первым детерминированным алгоритмом со сложностью выполнения быстрее, чем O(\sqrt{n}).

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

Для обозначения сложности принята L-нотация[3]:

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

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

Алгоритм Диксона[править | править вики-текст]

Сложность L_n(1/2,\;2\sqrt{2}).

Факторизация методом непрерывных дробей[править | править вики-текст]

Сложность L_n(1/2,\;\sqrt{2})[23].

Метод квадратичного решета[править | править вики-текст]

Сложность L_n(1/2,\;1)[23].

Данный метод с использованием нескольких многочленов эффективен и достаточно легко реализуем на компьютере. Есть основания полагать, что он является наилучшим из известных алгоритмов факторизации для n < 10^{110} (не считая метод факторизации с помощью эллиптических кривых, который в некоторых случаях может работать быстрее. Стоит так же заметить, что для чисел n > 10^{110} алгоритмы решета числового поля сработают быстрее, чем метод квадратичного решета[24].

Факторизация Ленстры с помощью эллиптических кривых[править | править вики-текст]

Сложность L_p(1/2,\;\sqrt{2}), где p — наименьшее простое, которое делит n[25].

Параметры a, x, y выбираются случайно. Значения w,v следует выбирать эмпирически, рассмотрев некоторую серию возрастающих значений[25]. На практике при заданных n, v, w алгоритм заключается в том, чтобы выполнить алгоритм с одной кривой. Это повторяется до тех пор, пока n не разложится на множители или пока время, отведенное для алгоритма, не закончится.

Существуют модификации алгоритма, позволяющие работать с несколькими кривыми одновременно[25].

Решето числового поля[править | править вики-текст]

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

Применение в криптографии[править | править вики-текст]

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

Текущее состояние[править | править вики-текст]

В марте 1994 года с помощью двойной вариации множественного полиномиального QS командой математиков под руководством Ленстры было разложено на множители 129-разрядное (428 битовое) число. Вычисления выполнялись добровольцами в Internet — в течение восьми месяцев трудились 600 человек и 1600 компьютеров. Компьютеры соединялись по электронной почте, передавая свои результаты в центральное хранилище, где выполнялся окончательный анализ. В этих вычислениях использовались QS и теория пятилетней давности, NFS мог бы ускорить выполнение расчетов. Группа ученых сделала вывод о том, что широко используемые 512-битовые модули RSA могут быть вскрыты организацией, готовой потратить несколько миллионов долларов и подождать несколько месяцев[26].

С целью развития искусства разложения на множители RSA Data Security, Inc. в марте 1991 года объявило о программе RSA Factoring Challenge(состязание RSA по разложению на множители). Состязание состоит в разложении на множители ряда трудных чисел, каждое из которых является произведением двух простых чисел примерно одинакового размера. Каждое простое число было выбрано конгруэнтным 2 по модулю 3. Всего было предложено 42 числа, по одному в диапазоне от 100 до 500 разрядов с шагом в 10 разрядов (плюс одно дополнительное, 129-разрядное число. Подробнее: RSA Factoring Challenge[en][26].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

на русском языке
на английском языке