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

Схематическая иллюстрация факторизации числа 525.

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

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

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

История

Задача поиска эффективных способов разложения целых чисел на множители интересовала математиков с давних времён, особенно специалистов в области теории чисел . Существуют предположения о том, что Ферма был одним из первых, кто предложил метод разложения, заключающийся в том, чтобы представить число в виде разности квадратов , а затем, вычисляя , попытаться найти нетривиальный делитель . Данный способ позволяет находить два мало различающихся по величине делителя числа быстрее, чем простой перебор делителей .

Далее Лежандр обнаружил, что при таком подходе достаточно получить сравнение , и использовал для этого цепные дроби. Также Эйлером и Гауссом были предложены некоторые способы нахождения чисел, связанных этим сравнением .

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

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

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

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

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

Как правило, на вход таких алгоритмов подаётся число , которое необходимо факторизовать, состоящее из символов (если представлено в двоичном виде) . При этом алгоритм ищет первый простой делитель, после чего, при необходимости, можно запустить алгоритм заново для дальнейшей факторизации. Также, прежде чем начинать факторизацию большого числа, следует убедиться в том, что оно не простое. Для этого достаточно пройти тест числа на простоту. Эта задача детерминированно разрешима за полиномиальное время .

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

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

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

Перебор возможных делителей

Сложность или .

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

Метод факторизации Ферма

Сложность или .

Идея алгоритма заключается в поиске таких чисел и , что факторизуемое число n представимо в виде: . Как и метод пробного деления, обычно не применяется на практике для факторизации больших чисел, так как имеет экспоненциальную сложность. Метод реализуем без операции деления, а только лишь с операциями сложения и вычитания . Если , при условии того, что и — простые числа, не сильно различающиеся по величине, то метод Ферма факторизует n достаточно быстро .

ρ-алгоритм Полларда

Сложность .

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

Алгоритм Ленстры

Сложность .

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

Алгоритм Полларда — Штрассена

Сложность .

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

Метод квадратичных форм Шенкса

Гарантированная сложность и при верности гипотезы Римана .

В отличие от алгоритма Полларда - Штрассена не требует выделения больших объёмов памяти, к тому же имеет достаточно простые расчётные формулы .

P-1 алгоритм Полларда

Сложность .

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

Метод Лемана

Сложность .

В настоящее время алгоритм представляет скорее исторический, чем практический интерес, так как этот алгоритм был первым детерминированным алгоритмом со сложностью выполнения быстрее, чем .

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

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

где — число подлежащее факторизации, и — некоторые константы.

Алгоритм Диксона

Сложность .

Факторизация методом непрерывных дробей

Сложность .

Метод квадратичного решета

Сложность .

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

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

Сложность , где — наименьшее простое, которое делит .

Параметры выбираются случайно. Значения следует выбирать эмпирически, рассмотрев некоторую серию возрастающих значений . На практике при заданных алгоритм заключается в том, чтобы выполнить алгоритм с одной кривой. Это повторяется до тех пор, пока не разложится на множители или пока время, отведённое для алгоритма, не закончится.

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

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

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

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

Предполагаемая большая вычислительная сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом , таких как 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-разрядное число. Подробнее: .

Примечания

  1. , с. 107.
  2. , с. 7—8.
  3. Gardner M. (англ.) // Scientific American — New York City: NPG , 1977. — Vol. 237, Iss. 2. — P. 120—124. — 5 p. — ISSN ; —
  4. , с. 9.
  5. , с. 48.
  6. , с. 52.
  7. , с. 142—143.
  8. , с. 424.
  9. , с. 52—54.
  10. , с. 57.
  11. , с. 431.
  12. , с. 64.
  13. , с. 63.
  14. , с. 62.
  15. , с. 73.
  16. , с. 69.
  17. , с. 73—74.
  18. .
  19. JASON E. GOWER AND SAMUEL S. WAGSTAFF, JR. // MATHEMATICS OF COMPUTATION. 24 августа 2017 года.
  20. , с. 62.
  21. , с. 57.
  22. , с. 55.
  23. , с. 56.
  24. , с. 151.
  25. , с. 78.
  26. , с. 87.
  27. , с. 92.
  28. , с. 113.
  29. , 11.4.
  30. , с. 93.
  31. , с. 87.
  32. , par.11.4.

Литература

на русском языке
  • Коблиц Н. — 2-е издание — М. : , 2001. — 254 с. — ISBN 978-5-85484-014-9 , 978-5-85484-012-5
  • М. : МЦНМО , 2002. — 104 с. — ISBN 978-5-94057-060-8
  • М. : МЦНМО , 2003. — 328 с. — ISBN 978-5-94057-103-2
  • : учебное пособие — Казань: Казанский университет , 2011. — 190 с.
  • М. : Московский государственный институт электроники и математики , 2012. — 224 с. — ISBN 978-5-94506-320-4
  • Кнут, Д. Искусство программирования = The Art of Computer Programming. — Москва: Вильямс, 2007. — Т. 2. — 832 с. — ISBN 978-5-8459-0081-4 .
  • Введение в криптографию / Ященко, В. В.. — Москва: МЦНМО , 1999. — 272 с. — ISBN 5-900916-40-5 .
  • Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — Москва: Триумф, 2002. — 816 с. — 3000 экз. ISBN 5-89392-055-4 .
на английском языке
  • Bressoud, D. M. . — N. Y. : Springer-Verlag, 1989. — 260 p. — ISBN 0-387-97040-1 .
  • Mahoney, M. S. . — 2. — Princeton: Princeton Univercity Press, 1994. — P. —332. — 438 p. — ISBN 0-691-03666-7 .
Источник —

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