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

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

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

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

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

Дано составное целое нечетное число n. Нужно найти его нетривиальный делитель d, 1 < d < n.

Случайным образом выбирается эллиптическая кривая

E\colon\quad y^2=x^3 +ax+b,

где a, b \in \mathbb{Z}_n, и некоторая точка P = \left({x,y}\right) на ней. Если попытка разложения окажется неудачной, следует взять другие E и P и повторить алгоритм сначала.

1. Выбирается целое число k, делящееся на степени малых простых чисел (не больших некоторого B), не превосходящих C, то есть

k = \prod_{\ell \le B} \ell^{\alpha_i},

где \alpha_i = \left\lfloor\log_{\ell} C\right\rfloor — наибольший из возможных показателей, при котором \ell^{\alpha_i} \le C.

2. Вычисление kP (все действия производятся по модулю n)

kP = \underbrace{P \boxplus \dots \boxplus P}_k,

где \boxplus — операция сложения, определенная по групповому закону.

Вычисления проводятся до тех пор, пока при попытке найти число, обратное к 2y_p (см. групповой закон) не появляется число, не взаимно простое с n. Это произойдёт при таком k=k_1, что k_1 P = O, то есть порядок P в группе E по модулю n является делителем k_1.

3. При применении алгоритма Евклида вместо обращения знаменателя по модулю n, получаем нетривиальный наибольший общий делитель этого знаменателя и n, то есть, собственный делитель числа n.

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

Если числа p и q — два простых делителя числа n, то эллиптическая кривая y2 = x3 + ax + b (mod n) соответствует двум эллиптическим кривым: по модулю p и по модулю q. Эти две кривые с заданной операцией сложения точек образуют группы, содержащие Np и Nq элементов, соответственно. По теореме Лагранжа для любой точки Р на исходной кривой по модулю p из равенства kP=\infty для минимального положительного числа k следует, что k делит Np (в частности, N_p P=\infty). Аналогичное утверждение справедливо и для кривой по модулю q. Для случайно выбранной эллиптической кривой порядки Np и Nq являются случайными числами, близкими к p+1 и q + 1, соответственно (см. ниже). Поэтому маловероятно, что большинство простых делителей Np и Nq совпадают, и вполне вероятно, что при вычислении eP мы столкнёмся с некоторыми kP=\infty по модулю р, но не по модулю q, или наоборот. Если это так, то kP не существует на исходной кривой, а в вычислениях мы нашли такое v, что либо НОД (v, p) = p, либо НОД (v, q) = q, но не одновременно. Тогда НОД (v, n) является нетривиальным делителем числа n.

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

Допустим, нам нужно факторизовать число 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\cdot14 - 5.

2. Теперь вычислим P_3=3!P=6P.

  • Тангенс угла наклона касательной в точке 2P составляет
~s=(3\cdot196+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 = (195045, 123227).

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

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

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

\exp((\sqrt{2} + o(1)) \sqrt{p \ln p \ln (\ln p)})

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

\exp((\sqrt{2}/2 + o(1)) \sqrt{p \ln p \ln (\ln p)})

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

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

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

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

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

  • Koblitz N. A. Course in number theory and cryptography. — Springer-Verlag, 1987.
  • Lenstra A. K., Lenstra H. W., Lovász L. (1982). «Factoring polynomials with rational coefficients». Math. Ann. 261.
  • Lenstra Jr., H. W. (1987). «Factoring integers with elliptic curves». Annals of Mathematics 126 (2): 649—673. MR89g:11125.
  • Trappe, W., Washington, L. C. Introduction to Cryptography with Coding Theory. — Second. — Pearson Prentice Hall, 2006. — ISBN 0-13-186239-1
  • Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казань: Казан. ун.. — 2011. — 190 с.

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