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

Факторизация с помощью эллиптических кривых (Шаблон:Lang-en, сокр. ECM) или Метод Ленстры факторизации с помощью эллиптических кривых (Шаблон:Lang-en) — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальную сложностьШаблон:Sfn. ECM является третьим по скорости работыШаблон:Sfn после общего метода решета числового поля и метода квадратичного решета.

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

Является лучшим алгоритмомШаблон:Sfn для поиска простых делителей длины 20-25 знаков (размером 64…83 бит), потому что его сложность в основном зависит от наименьшего простого делителя p, а не от факторизируемого числа.

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

Самый большой делитель, найденный использованием этого алгоритма, имеет длину 83 знака и был найден Райаном Проппером (Шаблон:Lang-en) 7 сентября 2013 г.

Алгоритм

Алгоритм факторизации (нахождения нетривиального делителя) натурального числа $n$Шаблон:Sfn:

1. Выбирается случайная эллиптическая кривая $E$ над ${\mathbb{Z}}_n$, с уравнением вида $E$: $y^2=x^3+ax+b(\mathrm{mod}n)$, на этой кривой выбирается нетривиальная точка $P(x_0,y_0)$. Это может быть сделано следующим образом:
   1. Случайным образом выбираются числа $x_0,y_0,a$ $\in$ ${\mathbb{Z}}_n$.
   2. Вычисляется $b=y_0^2-x_0^3-a{x}_0(\mathrm{mod}n)$.
2. Выбирается целое число $e$, являющиеся произведением большого количества малых чисел. Например, в качестве $e$ можно выбрать:
   • Факториал $B!$ некоторого небольшого числа $B$.
   • Произведение нескольких малых простых чисел в малых степенях. То есть выбираются простые числа $l_i$ (не превосходящие некоторое число $B$), и степени ${\alpha }_i$, такие, что результат возведения $l_i$ в соответствующую степень $l_i^{{\alpha }_i}$ не превосходит некоторого числа $C$:

   $e=\prod _{\ell \le B}{\ell }^{{\alpha }_i},$ где ${\alpha }_i=\lfloor {\log }_{\ell }C\rfloor$ — наибольший из возможных показателей, при котором ${\ell }^{{\alpha }_i}\le C$.

3. Вычисляется произведение $eP$ на эллиптической кривой $E$:

   $eP=\underset{e}{\underbrace{P⊞\dots ⊞P}}$, где $⊞$ — операция сложения, определённая по групповому закону.

   Операция сложения требует нахождения углового коэффициента отрезка, соединяющего суммируемые точки, и, следовательно, требует выполнения операции деления по модулю n. Операция деления по модулю осуществляется с помощью расширенного алгоритма Евклида. В частности, деление на некоторое число v (mod n) включает в себя нахождение Шаблон:Math. В случае Шаблон:Math $\ne$ 1, Шаблон:Math $\ne$ n, $⊞$-сложение не даст какой-то точки осмысленной на эллиптической кривой, из чего следует, что Шаблон:Math — нетривиальный делитель n. Исходя из этого, в процессе вычисления $eP$ возможны следующие случаи:

   • Если в процессе вычисления не встретились необратимые элементы Шаблон:Math, то необходимо выбрать другие эллиптическую кривую $E$ и точку $P(x_0,y_0)$ и повторить алгоритм сначала.
   • Если на каком-то этапе $e^{\prime }P=\underset{e^{\prime }}{\underbrace{P⊞\dots ⊞P}}=\mathrm{\infty }$, где ($e^{\prime }\le e$), то необходимо выбрать другие эллиптическую кривую $E$ и точку $P(x_0,y_0)$ и повторить алгоритм сначала, потому что точка $\mathrm{\infty }$ останется неизменной после дальнейших операций сложения.
   • Если на каком-то этапе вычислений Шаблон:Math $\ne$ 1 и Шаблон:Math $\ne$ n, то Шаблон:Math — искомый нетривиальный делитель n.

Обоснование

Уравнение $y^2=x^3+ax+b$, взятое по модулю числа n задаёт эллиптическую кривую $E$. Если числа p и q — два простых делителя числа n, то вышеупомянутое уравнение будет верно и при взятии по модулю p или по модулю q. То есть $E_1$: $y^2=x^3+ax+b(\mathrm{mod}p)$ и $E_2$: $y^2=x^3+ax+b(\mathrm{mod}q)$ задают, соответственно, две эллиптические кривые (меньшие, чем $E$). Однако $E_1$ и $E_2$ с заданной операцией сложения $⊞$ — не только эллиптические кривые: они также являются группами. Пусть они содержат N_p и N_q элементов, соответственно, тогда если:

1. $P$ — любая точка исходной кривой
2. $k_i$ — положительные числа, такие что: $k_{i}P=\mathrm{\infty }$ на $E_1$
3. $k$ — минимальное из $k_i$

То по теореме Лагранжа верно, что

1. $k$ — делитель $N_p$
2. $N_{p}P=\mathrm{\infty }$

Аналогичное утверждение справедливо и для кривой по модулю q.

Порядок группы точек, лежащих на эллиптической кривой $|E|$ над Z_p, согласно теореме Хассе ограничен: Шаблон:Math $\le |E|\le$p + 1 + 2√p

Для случайно выбранной эллиптической кривой порядки N_p и N_q являются случайными числами, ограниченными по теореме Хассе (см. ниже). Маловероятно, что большинство простых делителей N_p и N_q совпадают, и вероятно, что при вычислении eP встретится некоторый $kP=\mathrm{\infty }$ по модулю р, но не по модулю q, или наоборот. Если это так, то kP не существует на исходной кривой, а в вычислениях было найдено такое v, что либо НОД (v, p) = p, либо НОД (v, q) = q, но не одновременно. Тогда НОД (v, n) является нетривиальным делителем числа n.

ECM является доработкой более старого P-1 метода ПоллардаШаблон:Sfn. Алгоритм Шаблон:Math находит такие простые делители p, что Шаблон:Math — B-гладкое для некоторого небольшого B. Для любого e, кратного Шаблон:Math, и для любого a, взаимно простого с p по малой теорема Ферма верно, что Шаблон:Math. Тогда Шаблон:Math с большой вероятностью будет делителем n. Однако, Алгоритм Шаблон:Math не сработаетШаблон:Sfn, когда у Шаблон:Math есть большие простые делители. ECM в этом случае сработает корректно, потому что вместо рассмотрения мультипликативной группы над Z_p, порядок которой всегда равен Шаблон:Math, рассматривается группа случайной эллиптической кривой над конечным полем Z_p.

Порядок группы точек, лежащих на эллиптической кривой $|E|$ над Z_p, согласно теореме Хассе ограничен: Шаблон:Math $\le |E|\le$ Шаблон:Math. Представляется важным исследовать Шаблон:Sfn вероятность того, что в этом интервале может лежать некоторое гладкое число (в этом случае существуют кривые, порядок которых — гладкое число). Не существует доказательств того, что в интервале Хассе есть всегда некоторое гладкое число, однако использованием эвристических вероятностных методов, теоремы Канфилда-Эрдёша-Померанса(Шаблон:Lang-en)Шаблон:Sfn и L-нотации получается оценка, что достаточно взять Шаблон:Math кривых до получения гладкого порядка группы. Это эвристическая оценка хорошо применима на практике.

Пример

ФакторизацияШаблон:Sfn числа n = 455839.

Выбирается эллиптическая кривая и точка, лежащая на этой кривой

$y^2=x^3+5x-5,P=(1,1).$

Последовательно вычисляется 10!P:

1. Вычисляются координаты точки $P_2=2!P=2P$.

• Тангенс угла наклона касательной в точке P равен:

$s=\frac{dy}{dx}=\frac{3x^2+5}{2y}=4.$

• Координаты точки $P_2$:

$x_2=s^2-2x_1=14(\mathrm{mod}n),$

$y_2=s(x_1-x_2)-y=4(1-14)-1=-53(\mathrm{mod}n).$.

• Можно показать, что точка 2P действительно лежит на кривой:

$(-53{)}^2=2809=14^3+5\cdot 14-5.$

2. Вычисляется $P_3=3!P=6P$.

• Тангенс угла наклона касательной в точке 2P составляет

$s=(3\cdot 196+5)/(2(-53))=-593/106=322522(\mathrm{mod}n)$.

Для вычисления 593 / 106 по модулю n можно воспользоваться расширенным алгоритмом Евклида: 455839 = 4300·106 + 39, далее 106 = 2·39 + 28, далее 39 = 28 + 11, далее 28 = 2·11 + 6, далее 11 = 6 + 5, далее 6 = 5 + 1. Следовательно, НОД(455839, 106) = 1, и в обратную сторону: 1 = 6 — 5 = 2·6 — 11 = 2·28 — 5·11 = 7·28 — 5·39 = 7·106 — 19·39 = 81707·106 — 19·455839. Откуда 1/106 = 81707 (mod 455839), таким образом, −593 / 106 = 322522 (mod 455839).

• С учётом вычисленного s, вычисляются координаты точки 2(2P), так же, как это было сделано выше: 4P = (259851, 116255). Можно показать, что точка действительно лежит на нашей эллиптической кривой.
• Суммированием 4P и 2P находится $P_3=(179685,-28708)$.

3. Аналогичным образом можно вычислить $P_4=4!P$, $P_5=5!P$, и так далее. В момент вычисления 640P можно заметить, что требуется вычисление обратного элемента к 599 (mod 455839). Так как 455839 делится на 599, искомое разложение найдено: 455839 = 599·761.

Вычислительная сложность

Пусть наименьший делитель числа n равен p. Тогда количество выполняемых арифметических операций можно оценить величинойШаблон:Sfn: $e^{\sqrt{(2+o(1))\ln p\ln (\ln p)}}{\ln }^{2}n$ (или $L_p[1/2;\sqrt{2}]$ в L-нотации). Если заменить p на $n^{1/2}$, то получим субэкспоненциальную оценку сложности: $L_n[1/2;1]$.

Если сравнивать метод эллиптических кривых с другими методами факторизации, то этот метод относится к классу субэкспоненциальныхШаблон:Sfn методов факторизации, а, значит, работает быстрее любого экспоненциального метода. Если сравнивать его с методом квадратичного решета (QS) и методом решета числового поля (NFS), то все зависит от размера наименьшего делителя числа nШаблон:Sfn. Если число n выбрано как в RSA в виде произведения двух простых чисел примерно одинаковой длины, то метод эллиптических кривых имеет ту же оценку, что и метод квадратичного решета, но уступает методу решета числового поляШаблон:Sfn.

Алгоритм с проективными координатами

Прежде чем рассмотреть проективную плоскость над ${\mathbb{Z}}_n$, стоит рассмотреть обычную проективную плоскость над ℝ: вместо точек рассматриваются прямые, проходящие через 0. Прямая может быть задана с помощью ненулевой точки $(x,y,z)$ следующим образом: для любой точки $(x^{\prime },y^{\prime },z^{\prime })$ этой прямой ⇔ ∃ c ≠ 0, такие что x' = cx, y' = cy и z' = cz. В соответствии с этим отношением эквивалентности, пространство называется проективной плоскостью $(P^2)$. Точки плоскости $(x:y:z)$, соответствуют линиям трёхмерного пространства, проходящим через 0. Отметим, что точка $(0:0:0)$ не существует в этом пространстве, так она не задаёт прямой, проходящей через 0. Алгоритм Ленстры не предполагает обязательного использования поля ℝ, конечное поле также обеспечивает структуру группу над эллиптической кривой. Однако та же кривая, но с операциями над ${\mathbb{Z}}_n$, не образует группу, если $n$ не является простым числом. Метод факторизации с помощью эллиптических кривых использует особенности работы закона сложения в случаях, когда $n$ — не простое.

Алгоритм факторизации в проективных координатахШаблон:Sfn:. Нейтральный элемент в этом случае задается точкой на бесконечности $(0:1:0)$. Пусть Шаблон:Mvar — целое и положительное число, эллиптическая кривая $E(Z_n)=\{(x:y:z)\in P^2|y^{2}z=x^3+ax{z}^2+b{z}^3\}$.

1. Выбираются $x_P,y_P,a$ $\in$ ${\mathbb{Z}}_n$ (Шаблон:Mvar ≠ 0).
2. Вычисляется $b=y_P^2-x_P^3-a{x}_P$. Эллиптическая кривая Шаблон:Mvar задаётся как $y^2=x^3+ax+b$ (форма Вейерштрасса). С использованием проективных координат эллиптическую кривую можно записать в виде однородного уравнения $Z{Y}^2=X^3+a{Z}^{2}X+b{Z}^3$. $P=(x_P:y_P:1)$ лежит на этой кривой.
3. Выбирается верхняя граница $B\in \mathbb{Z}$. Примечание: факторы могут быть только в случае, когда порядок группы Шаблон:Mvar над ${\mathbb{Z}}_p$ — B-гладкое число. Это означает, что все простые факторы, Шаблон:Mvar над ${\mathbb{Z}}_p$ должны быть меньше или равны Шаблон:Mvar.
4. Вычисляется $k=$НОК$(1,\dots ,B)$.
5. Вычисляется $\underset{k}{\underbrace{P+P+\dots +P}}$ в кольце $E({\mathbb{Z}}_n)$. Важно заметить, что если |$E({\mathbb{Z}}_n)$| - B-гладкое, и Шаблон:Mvar — простое (в этом случае ${\mathbb{Z}}_n$ — поле), то $kP=(0:1:0)$. Однако в случае, если |$E({\mathbb{Z}}_p)$| - B-гладкое для некоторого числа Шаблон:Mvar, являющегося делителем Шаблон:Mvar, результат может быть не равен (0:1:0), потому что операции сложения и умножения могут не так хорошо работать, если Шаблон:Mvar не является простым числом. Таким образом возможно найти нетривиальный делитель Шаблон:Mvar.
6. Если делитель не был найден, то алгоритм повторяется с шага 2.

В пункте 5 вычисление $kP$ может быть невозможно, так как сложение двух точек над эллиптической кривой требует вычисления $(x_1-x_2{)}^{-1}$, что не всегда возможно, если Шаблон:Mvar не является простым числом. Возможно вычисление суммы двух точек следующим способом, не требующим простоты Шаблон:Mvar (не требующим того, чтобы ${\mathbb{Z}}_n$ являлось полем):

• ${\lambda }^{\prime }=y_1-y_2$,
• ${x_3}^{\prime }={{\lambda }^{\prime }}^2-x_1(x_1-x_2{)}^2-x_2(x_1-x_2{)}^2$,
• ${y_3}^{\prime }={\lambda }^{\prime }(x_1(x_1-x_2{)}^2-{x_3}^{\prime })-y_1(x_1-x_2{)}^3$,
• $R=P+Q=({x_3}^{\prime }(x_1-x_2):{y_3}^{\prime }:(x_1-x_2{)}^3)$, координаты в дальнейшем максимально упрощаются (нетривиальный делитель Шаблон:Mvar найден, если при упрощении возникает ошибка).

Использование кривых Эдвардса

Использование кривых Эдвардса позволяетШаблон:Sfn снизить количество модульных операций и уменьшить время выполнения алгоритма по сравнению с эллиптическими кривыми в форме Вейерштрасса ($y^2=x^3+ax+b(\mathrm{mod}p)$) и в форме Монтгомери ($B{y}^2=x^3+A{x}^2+x$).

Определение: Пусть $k$ — это поле, характеристикой которого не является число $2$, и пусть $d\in k\setminus \{0,1\}$. Тогда кривая Эдвардса $E_{E,d}$ определяется как $x^2+y^2=1+d{x}^2{y}^2.$ Существуют пять способов построить множество точек на кривой Эдварса: множество аффинных точек, множество проективных точек, множество инвертированных точек (Шаблон:Lang-en), множество расширенных точек (Шаблон:Lang-en) и множество завершённых точек (Шаблон:Lang-en). Например, множество аффинных точек задаётся как: $\{(x,y)\in A^2:x^2+y^2=1+d{x}^2{y}^2\}$.

Операция сложения: Закон сложения задаётся формулой $(e,f),(g,h)\mapsto (\frac{eh+fg}{1+degfh},\frac{fh-eg}{1-degfh})$.

Точка (0,1) — это нейтральный элемент, а обратная к точке $(e,f)$ это $(-e,f)$.

Другие формы получаются аналогично тому, как проективная кривая Вейерштрасса получается из аффинной кривой.

Пример сложения: Можно продемонстрировать закон сложения на примере эллиптической кривой в форме Эдвардса с d=2: ${\displaystyle }{x}^2+y^2=1+2x^2{y}^2$, и точки $P_1=(1,0)$ на ней. Предлагается проверить, что сумма P₁ с нейтральным элементом (0,1) равна P₁. Действительно:

$x_3=\frac{x_1{y}_2+y_1{x}_2}{1+d{x}_1{x}_2{y}_1{y}_2}=1$

$y_3=\frac{y_1{y}_2-x_1{x}_2}{1-d{x}_1{x}_2{y}_1{y}_2}=0$

У каждой эллиптической кривой в форме Эдварса существует точка порядка 4. Поэтому периодическая группа кривой Эдвардса над $\mathbb{Q}$ изоморфна ${\mathbb{Z}}_4,{\mathbb{Z}}_8,{\mathbb{Z}}_{12},{\mathbb{Z}}_2\times {\mathbb{Z}}_4$ или ${\mathbb{Z}}_2\times {\mathbb{Z}}_8$.

Для факторизации с помощью алгоритма Ленстры наиболее интересныШаблон:Sfn случаи ${\mathbb{Z}}_{12}$ и ${\mathbb{Z}}_2\times {\mathbb{Z}}_8$.

Пример кривой, которая содержит периодическую группу, изоморфную ${\mathbb{Z}}_{12}$:

$x^2+y^2=1+d{x}^2{y}^2$ с точкой $(a,b)$, лежащей на единичном круге с центром в точке (0,-1).

• $b\in (-2,0)\setminus \{-1,-1/2\},a^2=-(b^2+2b)$ и $d=-\frac{2b+1}{a^2{b}^2}=\frac{2b+1}{b^3(b+2)}$
• $a=\frac{u^2-1}{u^2+1},b=-\frac{(u-1{)}^2}{u^2+1}$ и $d=\frac{(u^2+1{)}^3(u^2-4u+1)}{(u-1{)}^6(u+1{)}^2},u\notin \{0,\pm 1\}.$

$a(1/u)=-a(u),b(1/u)=b(u),d(1/u)=d(u)$

См. также

• Факторизация
• Метод квадратичного решета
• P-1 метод Полларда
• Общий метод решета числового поля
• P+1 метод Уильямса
• Метод факторизации Ферма

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• • Факторизация методом эллиптических кривых, реализация в виде Java-апплета, объединяющая в себе ECM и методом самоинициализирующийся метод квадратичного решета (последний выбирается, когда он быстрее для конкретного случая).
• GMP-ECM, эффективная реализация ECM.
• ECMNet, простая реализация в виде сервер-клиент.
• pyecm, реализация ECM на Python 2.