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

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

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

Алгоритм

Дано составное целое нечетное число $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, то эллиптическая кривая y² = x³ + ax + b (mod n) соответствует двум эллиптическим кривым: по модулю p и по модулю q. Эти две кривые с заданной операцией сложения точек образуют группы, содержащие N_p и N_q элементов, соответственно. По теореме Лагранжа для любой точки Р на исходной кривой по модулю p из равенства $kP=\infty$ для минимального положительного числа k следует, что k делит N_p (в частности, $N_p P=\infty$). Аналогичное утверждение справедливо и для кривой по модулю q. Для случайно выбранной эллиптической кривой порядки N_p и N_q являются случайными числами, близкими к p+1 и q + 1, соответственно (см. ниже). Поэтому маловероятно, что большинство простых делителей N_p и N_q совпадают, и вполне вероятно, что при вычислении 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\cdot142+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)})$

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

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

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

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

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

См. также

• P+1 метод Уильямса
• Факторизация

Литература

• 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 с.

Ссылки

• http://www.alpertron.com.ar/ECM.HTM
• http://ecm.gforge.inria.fr/