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

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

Алгоритм


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

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

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

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

Обоснование


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

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

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

  1. k - делитель Np
  2. NpP=

 Аналогичное утверждение справедливо и для кривой по модулю q.\\Порядок группы точек, лежащих на эллиптической кривой |E| надZp, согласно теореме Хассе ограничен:|E|
 Для случайно выбранной эллиптической кривой порядкиNp и Nq являютсяслучайными числами, ограниченными по теореме Хассе (см. ниже).Маловероятно, что большинство простых делителейNp и Nq совпадают, ивероятно, что при вычислении eP встретится некоторый 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| надZp, согласно теореме Хассе ограничен:|E| . Представляется важным исследовать вероятность того, чтов этом интервале может лежать некоторое гладкое число (в этом случаесуществуют кривые, порядок которых - гладкое число). Не существуетдоказательств того, что в интервале Хассе есть всегда некоторое гладкоечисло, однако использованием эвристических вероятностных методов,теоремы Канфилда-Эрдоса-Померанса и L-нотации получается оценка, чтодостаточно взять кривых до получения гладкого порядка группы. Этоэвристическая оценка хорошо применима на практике.

Пример


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

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


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

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


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!P, P5=5!P, и такдалее. В момент вычисления 8!P можно заметить, что требуетсявычисление обратного элемента к 599 (mod 455839). Так как 455839 делитсяна 599, искомое разложение найдено: 455839 = 599·761.

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


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

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


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

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

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

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

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


 Использование кривых Эдвардса позволяет снизить количество модульныхопераций и уменьшить время выполнения алгоритма по сравнению сэллиптическими кривыми в форме Вейерштрасса(y2=x3+ax+b(modp)) и в форме Монтгомери(By2=x3+Ax2+x).
 Определение: Пусть k - это поле, характеристикой которого не являетсячисло 2, и пусть dk{0,1}. Тогда кривая ЭдвардсаEE,d определяется как x2+y2=1+dx2y2. Существуют пять способовпостроить множество точек на кривой Эдварса: множество афинных точек,множество проективных точек, множество инвертированных точек ,множество расширенных точек и множество завершённых точек .Например, множество афинных точек задаётся как:{(x,y)A2:x2+y2=1+dx2y2}.
 Операция сложения: Закон сложения задаётся формулой(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)