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

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

Алгоритм

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

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

где , и некоторая точка на ней. Если попытка разложения окажется неудачной, следует взять другие и и повторить алгоритм сначала.

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

где  — наибольший из возможных показателей, при котором .

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

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

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

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

Обоснование

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

Пример

Допустим, нам нужно факторизовать число 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. Тогда время работы алгоритма можно оценить величиной

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

Поскольку значение делителя 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. 89g: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/