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

Факторизация с помощью эллиптических кривых (англ. elliptic curve factorization method, сокр. ECM) или Метод Ленстры факторизации с помощью эллиптических кривых (англ. Lenstra elliptic curve factorization) — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальную сложность. ECM является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.

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

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

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

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

Алгоритм

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

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

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

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

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

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

   • Если в процессе вычисления не встретились необратимые элементы (mod n), то необходимо выбрать другие эллиптическую кривую $E$ и точку $P(x_{0},y_{0})$ и повторить алгоритм сначала.
   • Если на каком-то этапе $e'P=\underbrace {P\boxplus \dots \boxplus P} _{e'}=\infty$, где ($e'\leq e$), то необходимо выбрать другие эллиптическую кривую $E$ и точку $P(x_{0},y_{0})$ и повторить алгоритм сначала, потому что точка $\infty$ останется неизменной после дальнейших операций сложения.
   • Если на каком-то этапе вычислений НОД(v, n) $\neq$ 1 и НОД(v, n) $\neq$ n, то НОД(v, n) — искомый нетривиальный делитель n.

Обоснование

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

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

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

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

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

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

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

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

Порядок группы точек, лежащих на эллиптической кривой $|E|$ над Z_p, согласно теореме Хассе ограничен: p + 1 − 2√p $\leq |E|\leq$ p + 1 + 2√p. Представляется важным исследовать вероятность того, что в этом интервале может лежать некоторое гладкое число (в этом случае существуют кривые, порядок которых — гладкое число). Не существует доказательств того, что в интервале Хассе есть всегда некоторое гладкое число, однако использованием эвристических вероятностных методов, теоремы Канфилда-Эрдёша-Померанса(англ. Canfield–Erdős–Pomerance theorem) и L-нотации получается оценка, что достаточно взять L[√2/2, √2] кривых до получения гладкого порядка группы. Это эвристическая оценка хорошо применима на практике.

Пример

Факторизация числа 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{\pmod {n}},$

$y_{2}=s(x_{1}-x_{2})-y=4(1-14)-1=-53{\pmod {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{\pmod {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. Тогда количество выполняемых арифметических операций можно оценить величиной: $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]$.

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

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

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

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

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

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

• $\lambda '=y_{1}-y_{2}$,
• $x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}$,
• $y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}$,
• $R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})$, координаты в дальнейшем максимально упрощаются (нетривиальный делитель n найден, если при упрощении возникает ошибка).

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

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

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

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

Точка (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+dx_{1}x_{2}y_{1}y_{2}}}=1$

$y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{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}$.

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

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

$x^{2}+y^{2}=1+dx^{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 метод Уильямса
• Метод факторизации Ферма

Литература

• Koblitz N. A. Course in number theory and cryptography (неопр.). — Springer-Verlag, 1987.
• Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients (неопр.) // Math. Ann.. — 1982. — Т. 261.
• Lenstra Jr., H. W. Factoring integers with elliptic curves (англ.) // Annals of Mathematics : journal. — 1987. — Vol. 126, no. 2. — P. 649—673.
• Trappe, W., Washington, L. C. Introduction to Cryptography with Coding Theory (англ.). — Second. — Pearson Prentice Hall, 2006. — ISBN 0-13-186239-1.
• Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM using Edwards curves (англ.) // Mathematics of Computation : journal. — 2013. — Vol. 82. — P. 1139—1179. — doi:10.1090/S0025-5718-2012-02633-0.
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан. ун.. — 2011. — 190 с.
• David Bressoud and Stan Wagon. A Course in Computational Number Theory. — Key College Publishing/Springer, 2000. — С. 168—169. — 366 с. — ISBN 978-1-930190-10-8.
• Steven Galbraith. Mathematics of Public Key Cryptography. — Cambridge University Press, 2012. — С. 330—332. — 630 с. — ISBN 9781139012843.
• О. Н. Василенко. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2006. — 335 с. — ISBN 5-94057-103-4.
• W. Trappe and L. C. Washington. Introduction to Cryptography with Coding Theory. — Second. — Pearson Prentice Hall, 2006. — ISBN 0-13-186239-1.
• Parker D. Elliptic curves and Lenstra’s factorization algorithm (англ.) // University of Chicago: REU 2014. — 2014.
• E. R. Canfield, Paul Erdős, Carl Pomerance. On a Problem of Oppenheim concerning "Factorisatio Numerorum" (англ.) // Journal of number theory. — 1983. — Вып. 17.
• Richard P. Brent. Some integer factorization algorithms using elliptic curves (англ.) // Australian Computer Science Communications 8, 149-163. — 1998.
• H. W. Lenstra, JR. Elliptic Curves and Number-Theoretic Algorithms (англ.) // Proceedings of the International Congress of Mathematicians. — 1986. Архивировано 29 марта 2017 года.
• Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, Paul Zimmermann. Factorization of a 768-bit RSA modulus (англ.) // Cryptology ePrint Archive, Report 2010/006. — 2010.

Ссылки

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