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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сложность ${\displaystyle O(n)}$ или ${\displaystyle O(exp(N))}$ .

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

Пример модификации алгоритма

Шаг 1. Начальная установка. Присвоить ${\displaystyle x=2\lfloor {\sqrt {N}}\rfloor +1,y=1,r=\lfloor {\sqrt {N}}\rfloor ^{2}-N.}$ (Во время выполнения этого алгоритма величины x, y, r отвечают соответственно величинам ${\displaystyle 2x+1,2y+1,x^{2}-y^{2}-N}$ в уравнении ${\displaystyle N=uv=x^{2}-y^{2}(x={\dfrac {u+v}{2}},y={\dfrac {u-v}{2}})}$ . Должно соблюдаться условие ${\displaystyle |r|<x,y<x}$ .)

Шаг 2. Выполнено? Если ${\displaystyle r=0}$ , то выполнение алгоритма завершается. Имеем

${\displaystyle N={\frac {x-y}{2}}\cdot {\frac {x+y-2}{2}}}$

Шаг 3. Шаг по x. Присвоить ${\displaystyle r=r+x}$ и ${\displaystyle x=x+2}$ .

Шаг 4. Шаг по y. Присвоить ${\displaystyle r=r-y}$ и ${\displaystyle y=y+2}$ .

Шаг 5. Проверить r. Если ${\displaystyle r>0}$ , то возвратиться к шагу 4, иначе возвратиться к шагу 2.

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

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

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

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

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

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

Пример модификации алгоритма

Пусть ${\displaystyle r,s,n}$ — натуральные числа, удовлетворяющие условиям ${\displaystyle 1\leq r<s<n;\;n^{1/3}<s;\;\gcd(r,s)=1}$

Шаг 1. С помощью обобщённого алгоритма Евклида найти ${\displaystyle r^{*}\in \mathbb {N} ,rr^{*}\equiv 1\mod s}$ . Найти ${\displaystyle r'}$ такое, что ${\displaystyle r'\equiv r^{*}n\mod s,0\leq r'<s}$ .

Шаг 2. Для очередного значения ${\displaystyle i=0,1,2,...}$ найти числа ${\displaystyle a_{i},b_{i},c_{i}}$ по следующим правилам:

${\displaystyle a_{0}=s,\;b_{0}=0,\;c_{0}=0}$ ${\displaystyle a_{1}=rr'\mod s,0<a_{1}\leq s,\;b_{1}=1,\;c_{1}\equiv {\frac {n-rr'}{s}}r^{*}(\mod s)}$

при ${\displaystyle i\geq 2}$ :

${\displaystyle a_{i}=a_{i-2}-q_{i}a_{i-1},\;\;b_{i}=b_{i-2}-q_{i}b_{i-1},\;\;c_{i}=c_{i-2}-q_{i}c_{i-1}(\mod s)}$

${\displaystyle q_{i}}$ — частное от деления ${\displaystyle a_{i-2}}$ на ${\displaystyle a_{i-1}}$ , за исключением случая, когда ${\displaystyle i}$ нечётно и остаток от деления равен нулю.

Шаг 3. Для очередного выбора ${\displaystyle a_{i},b_{i},c_{i}}$ найти все целые числа ${\displaystyle c}$ , удовлетворяющие условиям

${\displaystyle c=c_{i}\mod s}$ ,

${\displaystyle |c|<s,\;\;\;\;\;\;}$ если ${\displaystyle i}$ четное,

${\displaystyle 2a_{i}b_{i}\leq c\leq {\frac {n}{s^{2}}}+a_{i}b_{i},\;\;}$ если ${\displaystyle i}$ нечетное.

Шаг 4. Для каждого c из шага 3 решить в целых числах систему уравнений

${\displaystyle \left\{{\begin{array}{rcl}xa_{i}+yb_{i}\;\;\;\;\;\;&=&c\\(xs+r)(ys+r')&=&n\\\end{array}}\right.}$

Если ${\displaystyle x}$ и ${\displaystyle y}$ окажутся неотрицательными целыми числами, то добавить ${\displaystyle xs+r}$

Шаг 5. Если ${\displaystyle a_{i}=0}$ , то алгоритм заканчивает работу. Иначе, возвращаемся на шаг 2 к следующему значению ${\displaystyle i}$ .

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

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

Данный алгоритм имеет оценку сложности схожую с методом квадратичных форм Шенкса (что является наилучшей среди детерминированных алгоритмов факторизации), однако требует выделение ${\displaystyle O(n^{1/4}\log n)}$ памяти. Он может использоваться непосредственно для факторизации не очень больших целых чисел, а также в качестве вспомогательного алгоритма в субэкспоненциальном методе Диксона и для ускорения вычислений второго этапа метода факторизации с помощью эллиптических кривых .

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

Гарантированная сложность ${\displaystyle O(n^{1/4+\varepsilon })}$ и при верности гипотезы Римана ${\displaystyle O(n^{1/5+\varepsilon })}$ .

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

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

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

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

Метод Лемана

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

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

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

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

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

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

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

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

Пример алгоритма

Шаг 1. Выбрать случайное ${\displaystyle b,1<b<n}$ , и вычислить ${\displaystyle b^{2}\mod m}$ .

Шаг 2. Пробными делениями попытаться разложить ${\displaystyle b^{2}\mod m}$ на простые множители из факторной базы.

Шаг 3. Если ${\displaystyle b}$ является ${\displaystyle B}$ -числом, т.е. ${\displaystyle b^{2}\mod n=\prod \limits _{p\in B}p^{\alpha _{p}(b)}}$ , то запомнить ${\displaystyle {\vec {\alpha }}(b)}$ и ${\displaystyle {\vec {\varepsilon }}(b)}$ . Повторять процедуру генерации чисел ${\displaystyle b}$ до тех пор, пока не будет найдено ${\displaystyle m=h+1}$ ${\displaystyle B}$ -чисел ${\displaystyle b_{1},...,b_{m}}$ .

Шаг 4. Найти (например, решая с помощью алгоритма последовательного исключения неизвестных Гаусса однородную систему линейных уравнений ${\displaystyle x_{1}{\vec {\varepsilon }}(b_{1})\oplus ...\oplus x_{m}{\vec {\varepsilon }}(b_{m})={\vec {0}}}$ относительно неизвестных ${\displaystyle (x_{1},...,x_{m})}$ ) соотношение линейной зависимости

${\displaystyle {\vec {\varepsilon }}(b_{i_{1}})\oplus ...\oplus {\vec {\varepsilon }}(b_{i_{t}})={\vec {0}},\;\;\;\;\;\;1<t\leq m.}$

Положить

${\displaystyle x=b_{i_{1}}...b_{i_{t}},\;\;\;\;\;\;y=\prod \limits _{p\in B}p^{{\frac {1}{2}}({\vec {\alpha _{p}}}(b_{i_{1}})+...+{\vec {\alpha _{p}}}(b_{i_{t}}))}}$

Шаг 5. Проверить ${\displaystyle x\equiv \pm y(\mod n)}$ . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение

${\displaystyle n=u\cdot v,\;\;\;\;\;\;u=(x+y,n),\;\;\;\;\;\;v=(x-y,n)}$ .

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

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

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

Сложность ${\displaystyle L_{n}(1/2,\;1)}$ .

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

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

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

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

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

Описание алгоритма

На вход алгоритма поступает число ${\displaystyle n}$ , которое необходимо факторизовать, параметры ${\displaystyle v,w\in \mathbb {N} }$ , зависящие от ${\displaystyle n}$ , кроме того, задаются ${\displaystyle a,x,y\in \mathbb {Z} /n\mathbb {Z} }$ такие, что ${\displaystyle P=(x:y:1)\in \mathbb {V} _{n}}$ и для ${\displaystyle b\equiv y^{2}-x^{3}-ax\mod n}$ выполнено условие ${\displaystyle 6(4a^{3}+27b^{2})\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$ . Алгоритм находит натуральный делитель ${\displaystyle d}$ числа ${\displaystyle n,1<d<n}$ .

Для каждого ${\displaystyle r\in \mathbb {N} ,2\leq r\leq w}$ , полагается

${\displaystyle e(r)=max\{m|m\in Z_{\geq 0},r^{m}\leq v+2{\sqrt {v}}+1\}}$

А также

${\displaystyle k=\prod \limits _{2\leq r\leq w}r^{e(r)}}$ , ${\displaystyle r}$ — простые.

Пусть ${\displaystyle P=(x:y:1\in \mathbb {V} _{n})}$ . Тогда ${\displaystyle P}$ лежит на эллиптической кривой ${\displaystyle E_{a,b}}$ над ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ , определённой уравнением ${\displaystyle Y^{2}=X^{3}+aX+b}$ . Необходимо вычислить точку ${\displaystyle kP}$ по правилам арифметики над эллиптическими кривыми. Если в ходе вычисления найден делитель ${\displaystyle d}$ числа ${\displaystyle n}$ , то ${\displaystyle n}$ разложилось на множители. Если найден ${\displaystyle kP}$ , а делитель ${\displaystyle d}$ не найден, то алгоритм завершает работу и выдаёт сообщение о неудачной попытке факторизации.

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

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

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

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

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

Примечания

Литература

на русском языке

• Коблиц Н. — 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 .