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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Алгоритм[править | править вики-текст]

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

  1. Выбирается случайная эллиптическая кривая над , с уравнением вида : , на этой кривой выбирается нетривиальная точка . Это может быть сделано следующим образом:
    1. Случайным образом выбираются числа .
    2. Вычисляется .
  2. Выбирается целое число , являющиеся произведением большого количества малых чисел. Например, в качестве можно выбрать:
    • Факториал некоторого небольшого числа .
    • Произведение нескольких малых простых чисел в малых степенях. Т.е. выбираются простые числа (не превосходящие некоторое число ), и степени , такие, что результат возведения в соответствующую степень не превосходит некоторого числа :
    где  — наибольший из возможных показателей, при котором .
  3. Вычисляется произведение на эллиптической кривой :
    , где  — операция сложения, определенная по групповому закону.
    Операция сложения требует нахождения углового коэффициента отрезка, соединяющего суммируемые точки, и, следовательно, требует выполнения операции деления по модулю n. Операция деления по модулю осуществляется с помощью расширенного алгоритма Евклида. В частности, деление на некоторое число v (mod n) включает в себя нахождение НОД(vn). В случае НОД(vn) 1, НОД(vn) n, -сложение не даст какой-то точки осмысленной на эллиптической кривой, из чего следует, что НОД(vn) - нетривиальный делитель n. Исходя из этого, в процессе вычисления возможны следующие случаи:
    • Если в процессе вычисления не встретились необратимые элементы (mod n), то необходимо выбрать другие эллиптическую кривую и точку и повторить алгоритм сначала.
    • Если на каком-то этапе , где (), то необходимо выбрать другие эллиптическую кривую и точку и повторить алгоритм сначала, потому что точка останется неизменной после дальнейших операций сложения.
    • Если на каком-то этапе вычислений НОД(vn) 1 и НОД(vn) n, то НОД(vn) - искомый нетривиальный делитель n.

Обоснование[править | править вики-текст]

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

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

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

  1. - делитель

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

Для случайно выбранной эллиптической кривой порядки Np и Nq являются случайными числами, близкими к p+1 и q + 1, соответственно (см. ниже). Поэтому маловероятно, что большинство простых делителей Np и Nq совпадают, и высока вероятность, что при вычислении eP мы столкнёмся с некоторый по модулю р, но не по модулю 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 по малой теорема Ферма верно, что ae ≡ 1 (mod p). Тогда [Наибольший общий делитель с большой вероятностью даст делитель n. Однако, Алгоритм p − 1 не работает, когда уp -  есть большие простые делители. ECM в этом случае сработает корректно, потому что вместо рассмотрения мультипликативной грппы над Zp, порядок которой всегда равен p − 1, рассматривает группу случайной эллиптической кривой над конечным полем Zp.

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

Пример[править | править вики-текст]

Допустим, нам нужно факторизовать число n = 455839.

Возьмем эллиптическую кривую и точку, лежащую на этой кривой

Попробуем вычислить 10!P:

1. Для начала вычислим координаты точки .

  • Тангенс угла наклона касательной в точке P равен:
  • Находим координаты точки :
.
  • Проверяем, что точка 2P действительно лежит на кривой:

2. Теперь вычислим .

  • Тангенс угла наклона касательной в точке 2P составляет
.
Для вычисления 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 находим .

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

Вычислительная сложность[править | править вики-текст]

Пусть наименьший делитель числа n равен p. Тогда время работы алгоритма можно оценить величиной:

Данная оценка выполняется в случае, если граница B1 выбрана близко к величине:

Поскольку значение делителя p неизвестно, то выбор значения B1 выполняется эмпирически, что несколько ухудшает практическую оценку сходимости. Отметим, что добавление в алгоритм второй стадии вычислений сохраняет общую асимптотическую оценку, хотя обеспечивает большой практический прирост скорости сходимости алгоритма.

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

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

Примечания[править | править вики-текст]

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]