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

Факторизация с помощью эллиптических кривых (, сокр. ECM) или Метод Ленстры факторизации с помощью эллиптических кривых  — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальную сложность. ECM является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.
 На практике лучше всего подходит для нахождения небольших простых делителей числа, и поэтому считается узкоспециализированным алгоритмом. Является лучшим алгоритмом для поиска простых делителей длины 20-25 знаков (размером 64...83 бит), потому что его сложность в основном зависит от наименьшего простого делителя p, а не от факторизируемого числа.
 Часто используется для выявления (отбрасывания) небольших простых делителей числа. Если полученное после работы алгоритма число все еще является составным, то остальные сомножители — большие числа, и для дальнейшего разложения имеет смысл использовать более общие алгоритмы факторизации.
 Самый большой делитель, найденный использованием этого алгоритма, имеет длину 83 знака и был найден Райаном Проппером 7 сентября 2013г.

Алгоритм


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

  1. Выбирается случайная эллиптическая кривая EE над ZnZn, с уравнением вида EE: y2=x3+ax+b(modn)y2=x3+ax+b(modn), на этой кривой выбирается нетривиальная точка P(x0,y0)P(x0,y0). Это может быть сделано следующим образом:
    1. Случайным образом выбираются числа x0,y0,ax0,y0,a ZnZn.
    2. Вычисляется b=y20x30ax0(modn)b=y20x30ax0(modn).

  2. Выбирается целое число ee, являющиеся произведением большого количества малых чисел. Например, в качестве ee можно выбрать:
    • Факториал B!B! некоторого небольшого числа BB.
    • Произведение нескольких малых простых чисел в малых степенях. Т.е. выбираются простые числа lili (не превосходящие некоторое число BB), и степени αiαi, такие, что результат возведения lili в соответствующую степень lαiilαii не превосходит некоторого числа CC:

    e=Bαi,e=Bαi, где αi=logCαi=logC — наибольший из возможных показателей, при котором αiCαiC.
  3. Вычисляется произведение ePeP на эллиптической кривой EE:
    eP=PPeeP=PPe, где  — операция сложения, определенная по групповому закону.
      Операция сложения требует нахождения углового коэффициента отрезка, соединяющего суммируемые точки, и, следовательно, требует выполнения операции деления по модулю n. Операция деления по модулю осуществляется с помощью расширенного алгоритма Евклида. В частности, деление на некоторое число v (mod n) включает в себя нахождение . В случае 1, n, -сложение не даст какой-то точки осмысленной на эллиптической кривой, из чего следует, что - нетривиальный делитель n. Исходя из этого, в процессе вычисления ePeP возможны следующие случаи:
    • Если в процессе вычисления не встретились необратимые элементы , то необходимо выбрать другие эллиптическую кривую EE и точку P(x0,y0)P(x0,y0) и повторить алгоритм сначала.
    • Если на каком-то этапе eP=PPe=eP=PPe=, где (eeee), то необходимо выбрать другие эллиптическую кривую EE и точку P(x0,y0)P(x0,y0) и повторить алгоритм сначала, потому что точка останется неизменной после дальнейших операций сложения.
    • Если на каком-то этапе вычислений 1 и n, то - искомый нетривиальный делитель n.

Обоснование


 Уравнение y2=x3+ax+by2=x3+ax+b, взятое по модулю числа n задаёт эллиптическую кривую EE. Если числа p и q — два простых делителя числа n, то вышеупомянутое уравнение будет верно и при взятии по модулю p или по модулю q. То есть E1E1: y2=x3+ax+b(modp)y2=x3+ax+b(modp) и E2E2: y2=x3+ax+b(modq)y2=x3+ax+b(modq) задают, соответственно, две эллиптические кривые (меньшие, чем EE). Однако E1E1 и E2E2 с заданной операцией сложения - не только эллиптические кривые: они также являются являются группами. Пусть они содержат Np и Nq элементов, соответственно, тогда если:

  1. PP - любая точка исходной кривой
  2. kiki - положительные числа, такие что: kiP=kiP= на E1E1
  3. kk - минимальное из kiki

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

  1. kk - делитель NpNp
  2. NpP=NpP=

 Аналогичное утверждение справедливо и для кривой по модулю q.\\ Порядок группы точек, лежащих на эллиптической кривой |E||E| над Zp, согласно теореме Хассе ограничен: |E||E|
 Для случайно выбранной эллиптической кривой порядки Np и Nq являются случайными числами, ограниченными по теореме Хассе (см. ниже). Маловероятно, что большинство простых делителей Np и Nq совпадают, и вероятно, что при вычислении eP встретится некоторый kP=kP= по модулю р, но не по модулю q, или наоборот. Если это так, то kP не существует на исходной кривой, а в вычислениях было найдено такое v, что либо НОД (v, p) = p, либо НОД (v, q) = q, но не одновременно. Тогда НОД (v, n) является нетривиальным делителем числа n.
 ECM является доработкой более старого P-1 метода Полларда. Алгоритм находит такие простые делители p, что - B-гладкое для некоторого небольшого B. Для любого e, кратного , и для любого a, взаимно простого с p по малой теорема Ферма верно, что . Тогда с большой вероятностью будет делителем n. Однако, Алгоритм не сработает, когда у есть большие простые делители. ECM в этом случае сработает корректно, потому что вместо рассмотрения мультипликативной группы над Zp, порядок которой всегда равен , рассматривается группа случайной эллиптической кривой над конечным полем Zp.
 Порядок группы точек, лежащих на эллиптической кривой |E||E| над Zp, согласно теореме Хассе ограничен: |E||E| . Представляется важным исследовать вероятность того, что в этом интервале может лежать некоторое гладкое число (в этом случае существуют кривые, порядок которых - гладкое число). Не существует доказательств того, что в интервале Хассе есть всегда некоторое гладкое число, однако использованием эвристических вероятностных методов, теоремы Канфилда-Эрдоса-Померанса и L-нотации получается оценка, что достаточно взять кривых до получения гладкого порядка группы. Это эвристическая оценка хорошо применима на практике.

Пример


 Факторизация числа n = 455839.
 Выбирается эллиптическая кривая и точка, лежащая на этой кривой
y2=x3+5x5,P=(1,1).
y2=x3+5x5,P=(1,1).

 Последовательно вычисляется 10!P:
 1. Вычисляются координаты точки P2=2!P=2PP2=2!P=2P.
 :* Тангенс угла наклона касательной в точке P равен:


s=dydx=3x2+52y=4.s=dydx=3x2+52y=4.

 2. Вычисляется P3=3!P=6PP3=3!P=6P.
 :* Тангенс угла наклона касательной в точке 2P составляет


s=(3196+5)/(2(53))=593/106=322522(modn)s=(3196+5)/(2(53))=593/106=322522(modn).

  Для вычисления 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).

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

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


 Пусть наименьший делитель числа n равен p. Тогда количество выполняемых арифметических операций можно оценить величиной: e(2+o(1))lnpln(lnp)ln2ne(2+o(1))lnpln(lnp)ln2n (или Lp[1/2;2]Lp[1/2;2] в L-нотации). Если заменить p на n1/2n1/2, то получим субэкспоненциальную оценку сложности: Ln[1/2;1]Ln[1/2;1].
 Если сравнивать метод эллиптических кривых с другими методами факторизации, то этот метод относится к классу субэкспоненциальных методов факторизации, а, значит, работает быстрее любого экспоненциального метода. Если сравнивать его с методом квадратичного решета (QS) и методом решета числового поля (NFS), то все зависит от размера наименьшего делителя числа n. Если число n выбрано как в RSA в виде произведения двух простых чисел примерно одинаковой длины, то метод эллиптических кривых имеет ту же оценку, что и метод квадратичного решета, но уступает методу решета числового поля.

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


 Прежде чем рассмотреть проективную плоскость над ZnZn, стоит рассмотреть обычную проективную плоскость над ℝ: вместо точек рассматриваются прямые, проходящие через 0. Прямая может быть задана с помощью ненулевой точкой (x,y,z)(x,y,z) следующим обзазом: для любой точки (x,y,z)(x,y,z) этой прямой ⇔ ∃ c ≠ 0, такие что x' = cx, y' = cy и z' = cz. В соответствии с этим отношением эквивалентности, пространство называется проективной плоскостью (P2)(P2). Точки плоскости (x:y:z)(x:y:z), соответствуют линиям трёхмерного пространства, проходящим через 0. Отметим, что точка (0:0:0)(0:0:0) не существует в этом пространстве, так она не задаёт прямой, проходящей через 0. Алгоритм Ленстры не предполагает обязательного использования поля ℝ, конечное поле также обеспечивает структуру группу над эллиптической кривой. Однако та же кривая, но с операциями над ZnZn, не образует группу, если nn не является простым числом. Метод факторизации с помощью эллиптических кривых использует особенности работы закона сложения в случаях, когда nn - не простое.
 Алгоритм факторизации в проективных координатах:. Нейтральный элемент в этом случаё задается точкой на бесконечности (0:1:0)(0:1:0). Пусть - целое и положительное число, эллиптическая кривая E(Zn)={(x:y:z)P2 | y2z=x3+axz2+bz3}E(Zn)={(x:y:z)P2 | y2z=x3+axz2+bz3}.

  1. Выбираются xP,yP,axP,yP,a ZnZn ( ≠ 0).
  2. Вычисляется b=y2Px3PaxPb=y2Px3PaxP. Эллиптическая кривая задаётся как y2=x3+ax+by2=x3+ax+b (форма Вейерштрасса). С использованием проективных координат эллиптическую кривую можно записать в виде однородного уравнения ZY2=X3+aZ2X+bZ3ZY2=X3+aZ2X+bZ3. P=(xP:yP:1)P=(xP:yP:1) лежит на этой кривой.
  3. Выбирается верхняя граница BZBZ. Примечание: факторы могут быть только в случае, когда порядок группы над ZpZp - B-гладкое число. Это означает, что все простые факторы, над ZpZp должны быть меньше или равны .
  4. Вычисляется k=k=НОК(1,,B)(1,,B).
  5. Вычисляется P+P++PkP+P++Pk в кольце E(Zn)E(Zn). Важно заметить, что если E(Zn)E(Zn) - B-гладкое, и - простое (в этом случае ZnZn - поле), то kP=(0:1:0)kP=(0:1:0). Однако в случае, если E(Zp)E(Zp) - B-гладкое для некоторого числа , являющегося делителем , результат может быть не равен (0:1:0), потому что операции сложения и умножения могут не так хорошо работать, если не является простым числом. Таким образом возможно найти нетривиальный делитель .
  6. Если делитель не был найден, то алгоритм повторяется с шага 2.

 В пункте 5 вычисление kPkP может быть невозможно, так как сложение двух точек над эллиптической кривой требует вычисления (x1x2)1(x1x2)1, что не всегда возможно, если не является простым числом. Возможно вычисление суммы двух точек следующим способом, не требующим простоты (не требующим того, чтобы ZnZn являлось полем):

  • λ=y1y2λ=y1y2,
  • x3=λ2x1(x1x2)2x2(x1x2)2x3=λ2x1(x1x2)2x2(x1x2)2,
  • y3=λ(x1(x1x2)2x3)y1(x1x2)3y3=λ(x1(x1x2)2x3)y1(x1x2)3,
  • R=P+Q=(x3(x1x2):y3:(x1x2)3)R=P+Q=(x3(x1x2):y3:(x1x2)3), координаты в дальнейшем максимально упрощаются (нетривиальный делитель найден, если при упрощении возникает ошибка).

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


 Использование кривых Эдвардса позволяет снизить количество модульных операций и уменьшить время выполнения алгоритма по сравнению с эллиптическими кривыми в форме Вейерштрасса (y2=x3+ax+b(modp)y2=x3+ax+b(modp)) и в форме Монтгомери (By2=x3+Ax2+xBy2=x3+Ax2+x).
 Определение: Пусть kk - это поле, характеристикой которого не является число 22, и пусть dk{0,1}dk{0,1}. Тогда кривая Эдвардса EE,dEE,d определяется как x2+y2=1+dx2y2.x2+y2=1+dx2y2. Существуют пять способов построить множество точек на кривой Эдварса: множество афинных точек, множество проективных точек, множество инвертированных точек , множество расширенных точек и множество завершённых точек . Например, множество афинных точек задаётся как: {(x,y)A2:x2+y2=1+dx2y2}{(x,y)A2:x2+y2=1+dx2y2}.
 Операция сложения: Закон сложения задаётся формулой (e,f),(g,h)(eh+fg1+degfh,fheg1degfh)(e,f),(g,h)(eh+fg1+degfh,fheg1degfh).
 Точка (0,1) - это нейтральный элемент, а обратная к точке (e,f) это (e,f).
 Другие формы получаются аналогично тому, как проективная кривая Вейерштрасса получается из афинной кривой.
 Пример сложения: Можно продемонстрировать закон сложения на примере эллиптической кривой в форме Эдвардса с d=2: x2+y2=1+2x2y2, и точки P1=(1,0) на ней. Предлагается проверить, что сумма P1 с нейтральным элементом (0,1) равна P1. Действительно:
x3=x1y2+y1x21+dx1x2y1y2=1

y3=y1y2x1x21dx1x2y1y2=0

 У каждой эллиптической кривой в форме Эдварса существует точка порядка 4. Поэтому периодическая группа кривой Эдвардса над Q изоморфна Z4,Z8,Z12,Z2×Z4 или Z2×Z8.
 Для факторизации с помощью алгоритма Ленстры наиболее интересны случаи Z12 и Z2×Z8.
 Пример кривой, которая содержит периодическую группу, изоморфную Z12:
x2+y2=1+dx2y2 с точкой (a,b), лежащей на единичном круге с центром в точке (0,-1).

  • b(2,0){1,1/2},a2=(b2+2b) и d=2b+1a2b2=2b+1b3(b+2)
  • a=u21u2+1,b=(u1)2u2+1 и d=(u2+1)3(u24u+1)(u1)6(u+1)2,u{0,±1}.

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