Processing math: 100%

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

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

История


 Задача поиска эффективных способов разложения целых чисел на множителиинтересовала математиков с давних времен, особенно специалистов вобласти теории чисел. Существуют предположения о том, что Ферма былодним из первых, кто предложил метод разложения, заключающийся в том,чтобы представить число в виде разности квадратов n=x2y2, азатем, вычисляя gcd(n,xy), попытаться найти нетривиальный делительn. Данный способ позволяет находить два мало отличающихся по величинеделителя числа быстрее, чем простой перебор делителей.
 Файл:Rsa logo.pngthumb245x245pxСозданиеалгоритма RSA стимулировало бурные исследования в области факторизациицелых чисел.Лежандр обнаружил, что при таком подходе достаточно получитьсравнение x2y2modn, и использовал для этого цепные дроби.Также Эйлером и Гауссом были предложены некоторые способы нахождениячисел, связанных этим сравнением.
 Одним из ключевых моментов в развитии факторизации целых чисел былосоздание алгоритма RSA, что возобновило интерес ученых в данномнаправлении, так как имело практическое применение в области шифрования.Этот алгоритм был предложен в 1977 году тремя учеными РональдомРивестом, Ади Шамиром и Леонардом Адлеманом из МассачусетскогоТехнологического Института и назван по первым буквам фамилий авторовметодом RSA. Он основан на идее криптографии с открытым ключом и длявзлома системы необходимо выполнить разложение числа на простыесомножители. На момент публикации алгоритма RSA были известны методы,которые позволяли факторизовать числа, состоящие не более чем из 25—30цифр, а наиболее известным и применяемым все ещё оставался метод Ферма.Метод RSA позволяет факторизовывать числа из 100 и более десятичныхзнаков. Создатели, в свою очередь, пообещали за факторизацию числа из129 десятичных знаков символические сто долларов США.
 На популярность задачи факторизации также повлияла публикация в 1977году в журнале Scientific American Мартина Гарднера «Новый алгоритмшифрования, для взлома которого потребуются миллионы лет». Столь громкоеназвание было воспринято в качестве вызова всему математическомусообществу. В результате этой гонки было предложено несколько новых инестандартных идей факторизации.
 Эпопея с разложением 129-значного числа завершилась в 1994 году, когдаколлектив под руководством А. Ленстры, используя 1600 компьютеров,подготовил за 220 дней систему линейных уравнений, содержавшую болееполумиллиона неизвестных. Решение этой системы суперкомпьютером занялодва дня. Несмотря на то, что в то время уже были известны методы решетачислового поля, данный результат был получен с помощью алгоритмаквадратичного решета.

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


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

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



agraphПеребор возможныхделителей
Сложность O(nlog2n) или O(nlogn).
 Один из самых простых и очевидных алгоритмов факторизации, заключающийсяв том, чтобы последовательно делить факторизуемое число n нанатуральные числа от 1 до n. Формальнодостаточно делить только на простые числа в этом интервале, однако, дляэтого необходимо знать их множество. На практике составляется таблицапростых чисел и производится проверка небольших чисел (например, до216). Для очень больших чисел алгоритм не используется в силунизкой скорости работы.

agraphМетод факторизацииФерма
Сложность O(n) или O(exp(N)).
 Идея алгоритма заключается в поиске таких чисел A и B, чтофакторизуемое число n представимо в виде: n=A2B2=(AB)(A+B).Как и метод пробного деления, обычно не применяется на практике дляфакторизации больших чисел, так как имеет экспоненциальную сложность.Метод примечателен тем, что реализуем без операции деления, а тольколишь с операциями сложения и вычитания. Следует так же отметить, чтоесли n=pq, при условии того, что p и q — простые числа несильно отличающиеся по величине, то метод Ферма факторизует n достаточнобыстро.

agraphρ-алгоритмПолларда
Сложность O(n1/4).
 Алгоритм Полларда является вероятностным алгоритмом, позволяющимнаходить делитель составного числа n, работающим со сложностью,зависящей лишь от величины делителя, но не величины факторизуемого числаn. Это обуславливает удобство применимости данного алгоритма в техслучаях, когда другие алгоритмы, сложность которых зависит от n,становятся неэффективны. Примечателен так же тем, что существует вариантреализации такого алгоритма, при котором достаточно в памяти хранитьвсего 3 целых числа.

agraphАлгоритмЛенстры
Сложность O(n1/3log2n).
 Следует отметить, что несмотря на относительно неплохую эффективностьсреди экспоненциальных алгоритмов, в алгоритме Ленстры естьнеобходимость неоднократно вычислять квадратный корень в одном из шаговалгоритма, что, безусловно, является более трудоемким, чем сложение иливычитание.

agraphАлгоритм Полларда —Штрассена
Сложность O(n1/4log4n).
 Данный алгоритм имеет оценку сложности схожую с методом квадратичныхформ Шенкса (что является наилучшей среди детерминированных алгоритмовфакторизации), однако требует выделение O(n1/4logn) памяти. Онможет использоваться непосредственно для факторизации не очень большихцелых чисел, а также в качестве вспомогательного алгоритма всубэкспоненциальном методе Диксона и для ускорения вычислений второгоэтапа метода факторизации с помощью эллиптических кривых.

agraphМетод квадратичных формШенкса
 Гарантированная сложность O(n1/4+ε) и при верностигипотезы Римана O(n1/5+ε).
 В отличии от алгоритма Полларда - Штрассена не требует выделения большихобъёмов памяти, к тому же имеет достаточно простые расчётные формулы.

agraphP-1 алгоритмПолларда
Сложность O(n1/2logcn).
 Несмотря на экспоненциальную оценку сложности, алгоритм во всех случаяхбыстро находит небольшие простые делители n, потому что они являютсястепенно-гладкими для небольшой границы гладкости B. В практическихзадачах данный алгоритм обычно используется до применениясубэкспоненциальных алгоритмов факторизации, чтобы отделить небольшиепростые делители числа n.

agraphМетодЛемана
Сложность O(n1/3).
 В настоящее время алгоритм представляет скорее исторический, чемпрактический интерес, так как этот алгоритм был первым детерминированнымалгоритмом со сложностью выполнения быстрее, чем O(n).

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


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

Ln(α,c):=O(exp((c+o(1))(logn)α(loglogn)1α)),
 где n — число подлежащее факторизации, 0<α<1 и c —некоторые константы.

agraphАлгоритмДиксона
Сложность Ln(1/2,22).

agraphФакторизация методом непрерывныхдробей
Сложность Ln(1/2,2).

agraphМетод квадратичногорешета
Сложность Ln(1/2,1).
 Данный метод с использованием нескольких многочленов эффективен идостаточно легко реализуем на компьютере. Есть основания полагать, чтоон является наилучшим из известных алгоритмов факторизации дляn<10110 (не считая метод факторизации с помощью эллиптическихкривых, который в некоторых случаях может работать быстрее. Стоит так жезаметить, что для чисел n>10110 алгоритмы решета числового полясработают быстрее, чем метод квадратичного решета.

agraphФакторизация Ленстры с помощью эллиптическихкривых
Сложность Lp(1/2,2), где p — наименьшее простое,которое делит n.
 Параметры a,x,y выбираются случайно. Значения w,v следует выбиратьэмпирически, рассмотрев некоторую серию возрастающих значений. Напрактике при заданных n,v,w алгоритм заключается в том, чтобывыполнить алгоритм с одной кривой. Это повторяется до тех пор, пока nне разложится на множители или пока время, отведенное для алгоритма, незакончится.
 Существуют модификации алгоритма, позволяющие работать с несколькимикривыми одновременно.

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

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

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


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

Текущеесостояние


 В марте 1994 года с помощью двойной вариации множественногополиномиального QS командой математиков под руководством Ленстры былоразложено на множители 129-разрядное (428 битовое) число. Вычислениявыполнялись добровольцами в Интернете — в течение восьми месяцевтрудились 600 человек и 1600 компьютеров. Компьютеры соединялись поэлектронной почте, передавая свои результаты в центральное хранилище,где выполнялся окончательный анализ. В этих вычислениях использовалисьQS и теория пятилетней давности, NFS мог бы ускорить выполнениерасчетов. Группа ученых сделала вывод о том, что широко используемые512-битовые модули RSA могут быть вскрыты организацией, готовойпотратить несколько миллионов долларов и подождать несколько месяцев.
 С целью развития искусства разложения на множители RSA Data Security,Inc. в марте 1991 года объявило о программе RSA Factoring Challenge(состязание RSA по разложению на множители). Состязание состоит вразложении на множители ряда трудных чисел, каждое из которых являетсяпроизведением двух простых чисел примерно одинакового размера. Каждоепростое число было выбрано конгруэнтным 2 по модулю 3. Всего былопредложено 42 числа, по одному в диапазоне от 100 до 500 разрядов сшагом в 10 разрядов (плюс одно дополнительное, 129-разрядное число.Подробнее: .