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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Перебор делителей

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

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

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

Шаг 1. Начальная установка. Присвоить $t=0,k=0,n=N$(В ходе выполнения алгоритма переменные $t,k,n$ подчинены следующим условиям: $n=N/p_{1}...p_{t}$ и $n$ не имеет простых множителей, меньших $d_{k}$)

Шаг 2. $n=1?$ Если $n=1$, алгоритм заканчивается.

Шаг 3. Разделить. Присвоить $q=\lfloor n/d_{k}\rfloor ,r=n\mod d_{k}.$ (Здесь $q$ и $r$ соответственно частное и остаток от деления числа $n$ на $d_{k}$.)

Шаг 4. Остаток равен нулю? Если $r\neq 0$, то перейти к шагу 6.

Шаг 5. Множитель найден. Увеличить $t$ на $1$ и присвоить $p_{t}=d_{k},n=q$. Возвратиться к шагу 2.

Шаг 6. Частное мало? Если $q>d_{k}$, увеличить $k$ на 1 и возвратиться к шагу 3.

Шаг 7. n — простое число. Увеличить $t$ на $1$, присвоить $p_{t}=n$ и завершить выполнение алгоритма.

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

Основная статья: Метод факторизации Ферма

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

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

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

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

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

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

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

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

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

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

Основная статья: Ρ-алгоритм Полларда

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

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

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

Шаг 1. Выбираем небольшое число $x_{0}$ и строим последовательность чисел ${x_{k}},k=0,1,2,...,$ определяя каждое следующее $x_{k+1}$ по формуле: $x_{k+1}=x_{k}^{2}-1\mod n$

Шаг 2. Одновременно на каждом шаге $i$ вычисляем НОД $d$ числа $n$ и всевозможных разностей $|x_{i}-x_{j}|$, где $j<i$.

Шаг 3. Когда будет найден $d=$НОД$(n,|x_{i}-x_{j}|)$, отличный от $1$, вычисление заканчивается. Найденное $d$ является делителем $n$. Если $n/d$ не является простым числом, то процедуру можно продолжить, взяв вместо $n$ число $n/d$.

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

Основная статья: Детерминированный алгоритм факторизации Ленстры

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

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

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

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

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

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

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

при $i\geq 2$:

$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)$

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

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

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

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

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

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

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

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

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

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

Основная статья: Алгоритм Полларда — Штрассена

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

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

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

Теорема. Пусть $z\in \mathbb {N} ,y=z^{2}$. Тогда для любого натурального числа $t$ наименьший простой делитель числа $\gcd(n,y!)$ может быть найден за $O(z\log ^{2}z\log ^{2}t)$ арифметических операций.

Алгоритм. Положим $z=[n^{1/4}]+1,y=z^{2}>n^{1/2},t=n$. Далее с помощью алгоритма теоремы найдём наименьший простой делитель числа $\gcd(n,y!)$. Поскольку $y!$ делится на наименьший простой делитель $p$ числа $n(p\leq n^{1/2}<y)$, то алгоритм выдаст именно это число $p$.

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

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

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

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

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

Основная статья: P-1 метод Полларда

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

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

Оценка сложности по стадиям

Сложность первой стадии. $O(B_{1}\log B_{1}\log ^{2}N)$, где $B_{1}$ — граница

Сложность второй стадии. $O(\log ^{2}B_{2})+O(\log q_{\pi (B_{1})})+2(\pi (B_{2})-\pi (B_{1}))$, где $B_{2}$ — новая граница. $B_{2}>>B_{1}$

Метод Лемана

Основная статья: Метод Лемана

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

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

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

Шаг 1. Для всех $p$ от $2$ до $\lceil {\sqrt[{3}]{m}}\rceil$ выполнять:

Если $m\equiv 0\mod p$, то вернуть $p$ в качестве делителя числа m и завершить алгоритм.

Шаг 2. Для всех $b$ от $1$ до $\lceil {\sqrt[{3}]{m}}\rceil$ выполнять:

Шаг 2.1 Определить $k=0$ и $D=\left\lfloor {\frac {\sqrt[{6}]{m}}{4{\sqrt {b}}}}\right\rfloor +1$

Шаг 2.2 Определить $x=\lfloor {\sqrt {4bm}}\rfloor +k$ и $v=x^{2}-4bm$

Шаг 2.3 Если $v$ является полным квадратом, то определить $p=\gcd(m,x\pm v)$ и завершить алгоритм.

Шаг 2.4 Определить $k=k+1$.

Шаг 2.5 Если $k\geq D$, то вычислить новое значение $d$, в противном случае вернуться на шаг 2.2

Шаг 3. Запустить алгоритм с уведомлением, что факторизуемое число $m$ — простое.

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

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

$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}})$.

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

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

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

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

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

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

Положить

$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. Проверить $x\equiv \pm y(\mod n)$. Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение

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

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

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

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

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

Основная статья: Метод квадратичного решета

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

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

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

Основная статья: Метод эллиптических кривых

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

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

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

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

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

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

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

А также

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

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

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

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

• Специальный метод решета числового поля со сложностью $L_{n}(1/3,\;(32/9)^{\frac {1}{3}})$ (метод применим для факторизации чисел только специального вида);
• Общий метод решета числового поля со сложностью $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-разрядное число. Подробнее: RSA Factoring Challenge.

Литература

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

• Коблиц Н. Курс теории чисел и криптографии — 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. Factorization and Primality Testing. — N. Y.: Springer-Verlag, 1989. — 260 p. — ISBN 0-387-97040-1.
• Mahoney, M. S. The Mathematical Career of Pierre de Fermat. — 2. — Princeton: Princeton Univercity Press, 1994. — P. 324—332. — 438 p. — ISBN 0-691-03666-7.