Факторизация эллиптической кривой Ленстры

Факторизация эллиптической кривой Ленстры или метод факторизации эллиптической кривой (ECM ) - это быстрый, суб экспоненциальный алгоритм времени для целочисленной факторизации, который использует эллиптические кривые. Для факторинга общего назначения ECM является третьим по скорости известным методом факторинга. Вторым по скорости является многократное полиномиальное квадратичное сито, а самым быстрым является сито общего числового поля. Факторизация эллиптической кривой Ленстры названа в честь Хендрика Ленстры.

Практически говоря, ECM считается алгоритмом факторинга специального назначения, так как он наиболее подходит для поиска малых факторов. В настоящее время это все еще лучший алгоритм для делителей, не превышающих от 50 до 60 цифр, поскольку время его работы определяется размером наименьшего множителя p, а не размером номер n для факторизации. Часто ECM используется для удаления небольших множителей из очень большого целого числа с множеством множителей; если оставшееся целое число по-прежнему составное, то оно имеет только большие множители и факторизуется с использованием универсальных методов. Самый большой фактор, обнаруженный с помощью ECM, состоит из 83 десятичных цифр и был обнаружен 7 сентября 2013 года Р. Проппером. Увеличение количества тестируемых кривых увеличивает шансы нахождения фактора, но они не линейные с увеличением количества цифр.

• 1 Алгоритм
• 2 Почему алгоритм работает?
• 3 Пример
• 4 Алгоритм с проективными координатами
• 5 Скрученные кривые Эдвардса
• 6 Этап 2
• 7 GMP-ECM и EECM-MPFQ
• 8 Метод гиперэллиптической кривой (HECM)
• 9 Квантовая версия (GEECM)
• 10 См. Также
• 11 Ссылки
• 12 Внешние ссылки

Метод факторизации эллиптической кривой Ленстры для нахождения множителя данного натурального числа $n\; \{\backslash \; displaystyle\; n\}$работает следующим образом:

1. Выберите случайный эллиптический кривая над $Z\; /\; n\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\}\}$, с уравнением вида $y\; 2\; =\; x\; 3\; +\; ax\; +\; b\; (mod\; n)\; \{\backslash \; displaystyle\; y\; ^\; \{2\}\; =\; x\; ^\; \{3\}\; +\; ax\; +\; b\; \{\backslash \; pmod\; \{n\}\}\}$вместе с нетривиальным point $P\; (x\; 0,\; y\; 0)\; \{\backslash \; displaystyle\; P\; (x\_\; \{0\},\; y\_\; \{0\})\}$на нем.

   Это можно сделать, выбрав сначала случайным образом $x\; 0,\; y\; 0,\; a\; \in \; Z\; /\; n\; Z\; \{\backslash \; displaystyle\; x\_\; \{0\},\; y\_\; \{0\},\; a\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\}\}$, а затем установив $b\; =\; y\; 0\; 2\; -\; x\; 0\; 3\; -\; ax\; 0\; (mod\; n)\; \{\backslash \; displaystyle\; b\; =\; y\_\; \{0\}\; ^\; \{2\}\; -x\_\; \{0\}\; ^\; \{3\}\; -ax\_\; \{0\}\; \{\backslash \; pmod\; \{n\}\}\}$, чтобы убедиться, что точка находится на кривой.

2. Можно определить сложение двух точек на кривой, чтобы определить группу . Законы сложения приведены в статье об эллиптических кривых.

   . Мы можем формировать повторяющиеся кратные точки $P\; \{\backslash \; displaystyle\; P\}$: $[k]\; P\; =\; P\; +\dots \; +\; P\; (k\; раз)\; \{\backslash \; displaystyle\; [k]\; P\; =\; P\; +\; \backslash \; ldots\; +\; P\; \{\backslash \; text\; \{(k\; раз)\}\}\}$. Формулы сложения включают взятие модульного наклона хорды, соединяющей $P\; \{\backslash \; displaystyle\; P\}$и $Q\; \{\backslash \; displaystyle\; Q\}$, и, таким образом, разделение между остаточными классами по модулю $n\; \{\backslash \; displaystyle\; n\}$, выполняется с использованием расширенного алгоритма Евклида. В частности, деление на некоторый $v\; mod\; n\; \{\backslash \; displaystyle\; v\; \{\backslash \; bmod\; \{n\}\}\}$включает вычисление $gcd\; (v,\; n)\; \{\backslash \; displaystyle\; \backslash \; gcd\; (v,\; n)\}$.

   Предполагая, что мы вычисляем наклон в форме $u\; /\; v\; \{\backslash \; displaystyle\; u\; /\; v\}$с $gcd\; (u,\; v)\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; gcd\; (u,\; v)\; =\; 1\}$, тогда, если $v\; =\; 0\; mod\; n\; \{\backslash \; displaystyle\; v\; =\; 0\; \{\backslash \; bmod\; \{n\}\}\}$, результат сложение точки будет иметь вид $\infty \; \{\backslash \; displaystyle\; \backslash \; infty\}$, точка «на бесконечности», соответствующая пересечению «вертикальной» линии, соединяющей $P\; (x,\; y),\; P\; \prime \; (X,\; -\; y)\; \{\backslash \; displaystyle\; P\; (x,\; y),\; P\; \text{'}(x,\; -y)\}$и кривая. Однако, если $gcd\; (v,\; n)\; \ne \; 1,\; n\; \{\backslash \; displaystyle\; \backslash \; gcd\; (v,\; n)\; \backslash \; neq\; 1,\; n\}$, то добавление точки не даст значимой точки на Кривая; но, что более важно, $gcd\; (v,\; n)\; \{\backslash \; displaystyle\; \backslash \; gcd\; (v,\; n)\}$является нетривиальным множителем $n\; \{\backslash \; displaystyle\; n\}$.

3. Вычислить $[k]\; P\; \{\backslash \; displaystyle\; [k]\; P\}$на эллиптической кривой ($mod\; n\; \{\backslash \; displaystyle\; \{\backslash \; bmod\; \{n\}\}\}$), где $k\; \{\backslash \; displaystyle\; k\}$- произведение множества малых чисел: скажем, произведение малых простых чисел в малых степенях, как в алгоритме p-1, или фактор $B!\; \{\backslash \; displaystyle\; B!\}$для некоторых не слишком больших $B\; \{\backslash \; displaystyle\; B\}$. Это можно сделать эффективно, по одному небольшому фактору за раз. Скажем, чтобы получить $[B!\; ]\; P\; \{\backslash \; displaystyle\; [B!]\; P\}$, сначала вычисляем $[2]\; P\; \{\backslash \; displaystyle\; [2]\; P\}$, затем $[3]\; (\; [2]\; P)\; \{\backslash \; displaystyle\; [3]\; ([2]\; P)\}$, затем $[4]\; ([3!]\; P)\; \{\backslash \; displaystyle\; [4]\; ([3!]\; P)\}$и так далее. $B\; \{\backslash \; displaystyle\; B\}$выбрано достаточно маленьким, чтобы $B\; \{\backslash \; displaystyle\; B\}$добавление точек могло быть выполнено в разумные сроки.
   • Если мы закончим все вышеперечисленные вычисления, не обнаружив необратимых элементов ($mod\; n\; \{\backslash \; displaystyle\; \{\backslash \; bmod\; \{n\}\}\}$), это означает, что эллиптические кривые '(по модулю простых чисел) порядок не гладкий, поэтому нам нужно попробовать еще раз с другой кривой и начальной точкой.
   • Если мы встретим $gcd\; (v,\; n)\; \ne \; 1,\; m\; \{\backslash \; displaystyle\; \backslash \; gcd\; (v,\; n)\; \backslash \; neq\; 1,\; m\}$, все готово: это нетривиальный множитель $n\; \{\backslash \; displaystyle\; n\}$.

Временная сложность зависит от размера наименьшего простого множителя числа и может быть представлена ​​выражением exp [(√2 + o (1)) √ln p ln ln p], где p - наименьший фактор n или $L\; p\; [1\; 2,\; 2]\; \{\backslash \; displaystyle\; L\_\; \{p\}\; \backslash \; left\; [\{\backslash \; frac\; \{1\}\; \{2\}\},\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; right]\}$, в L-нотации.

Если p и q являются двумя простыми делителями n, то y = x + ax + b (mod n) подразумевает то же уравнение также по модулю p и модулю q. Эти две эллиптические кривые меньшего размера с добавлением $⊞\; \{\backslash \; displaystyle\; \backslash \; boxplus\}$теперь являются настоящими группами . Если эти группы имеют N p и N q элементов, соответственно, то для любой точки P на исходной кривой по теореме Лагранжа k>0 минимально такое, что $k\; P\; =\; \infty \; \{\backslash \; displaystyle\; kP\; =\; \backslash \; infty\}$на кривой по модулю p означает, что k делит N p ; кроме того, $N\; p\; P\; =\; \infty \; \{\backslash \; displaystyle\; N\_\; \{p\}\; P\; =\; \backslash \; infty\}$. Аналогичное утверждение верно для кривой по модулю q. Когда эллиптическая кривая выбирается случайным образом, тогда N p и N q являются случайными числами, близкими к p + 1 и q + 1, соответственно (см. Ниже). Следовательно, маловероятно, что большинство простых множителей N p и N q одинаковы, и весьма вероятно, что при вычислении eP мы встретим некоторое kP, равное ∞ по модулю p, но не по модулю q, и наоборот. В этом случае kP не существует на исходной кривой, и в вычислениях мы нашли некоторое v с либо gcd (v, p) = p, либо gcd (v, q) = q, но не обоими сразу. То есть gcd (v, n) дал нетривиальный множитель n.

ECM по своей сути является улучшением более старого алгоритма p - 1. Алгоритм p - 1 находит такие простые множители p, что p - 1 равно b-powersmooth для малых значений b. Для любого e, кратного p - 1 и любого a , относительно простого с p, по маленькой теореме Ферма мы имеем ≡ 1 (mod p). Тогда gcd (a - 1, n), скорее всего, даст множитель n. Однако алгоритм не работает, когда p - 1 имеет большие простые множители, как, например, в случае чисел, содержащих сильных простых чисел.

ECM преодолевает это препятствие, рассматривая группу случайной эллиптической кривой над конечным полем Zp, вместо того, чтобы рассматривать мультипликативная группа из Zp, которая всегда имеет порядок p - 1.

Порядок группы эллиптической кривой на Zpварьируется (довольно случайным образом) между p + 1 - 2√p и p + 1 + 2√p по теореме Хассе и, вероятно, будет гладким для некоторых эллиптических кривых. Хотя нет никаких доказательств того, что в интервале Хассе будет найден плавный групповой порядок, с использованием эвристических вероятностных методов, с подходящим образом оптимизированным выбором параметров и L-нотацией, мы можем ожидать попробовать кривые L [√2 / 2, √2], прежде чем получить плавный групповой порядок. Эта эвристическая оценка очень надежна на практике.

Следующий пример взят из Trappe Washington (2006) с некоторыми добавленными деталями.

Мы хотим разложить n = 455839 на множители. Выберем эллиптическую кривую y = x + 5x - 5 с точкой P = (1, 1) на ней и попробуем вычислить (10!) P.

Наклон касательной в некоторой точке A = (x, y) равен s = (3x + 5) / (2y) (mod n). Используя s, мы можем вычислить 2A. Если значение s имеет вид a / b, где b>1 и gcd (a, b) = 1, мы должны найти модульную инверсию b. Если он не существует, gcd (n, b) является нетривиальным множителем n.

Сначала мы вычисляем 2P. У нас s (P) = s (1,1) = 4, поэтому координаты 2P = (x ′, y ′) равны x ′ = s - 2x = 14 и y ′ = s (x - x ′) - y = 4 (1 - 14) - 1 = –53, все числа понятны (mod n). Просто чтобы убедиться, что этот 2P действительно находится на кривой: (–53) = 2809 = 14 + 5 · 14 - 5.

Затем мы вычисляем 3 (2P). У нас есть s (2P) = s (14, -53) = –593/106 (mod n). Используя алгоритм Евклида : 455839 = 4300 · 106 + 39, затем 106 = 2 · 39 + 28, затем 39 = 28 + 11, затем 28 = 2 · 11 + 6, затем 11 = 6 + 5, то 6 = 5 + 1. Следовательно, gcd (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. Следовательно, 106 = 81707 (мод 455839) и –593/106 = –133317 (мод 455839). Зная это s, мы можем вычислить координаты 2 (2P), как мы делали выше: 4P = (259851, 116255). Просто чтобы убедиться, что это действительно точка на кривой: y = 54514 = x + 5x - 5 (mod 455839). После этого мы можем вычислить $3\; (2\; P)\; =\; 4\; P\; ⊞\; 2\; P\; \{\backslash \; displaystyle\; 3\; (2P)\; =\; 4P\; \backslash \; boxplus\; 2P\}$.

Мы можем аналогичным образом вычислить 4! P и так далее, но 8 ! P требует инвертирования 599 (мод 455839). Алгоритм Евклида дает, что 455839 делится на 599, и мы нашли факторизацию 455839 = 599 · 761.

Причина, по которой это сработало, состоит в том, что кривая (mod 599) имеет 640 = 2,5 точек, а (mod 761) имеет 777 = 3,7 37 точек. Кроме того, 640 и 777 - это наименьшие положительные целые числа k такие, что kP = ∞ на кривой (mod 599) и (mod 761), соответственно. С 8! кратно 640, но не 777, мы имеем 8! P = ∞ на кривой (mod 599), но не на кривой (mod 761), следовательно, повторное сложение здесь прервалось, давая факторизацию.

Прежде чем рассматривать проективную плоскость над $(Z\; /\; n\; Z)\; /\; \sim ,\; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\; \})\; /\; \backslash \; sim,\}$сначала рассмотрим «нормальное» проективное пространство над ℝ: вместо точек изучаются прямые, проходящие через начало координат. Линия может быть представлена ​​как ненулевая точка $(x,\; y,\; z)\; \{\backslash \; displaystyle\; (x,\; y,\; z)\}$в соответствии с отношением эквивалентности ~, заданным следующим образом: $(Икс,\; Y,\; Z)\; \sim \; (Икс\; \text{'},\; Y\text{'},\; Z\; \text{'})\; \{\backslash \; Displaystyle\; (х,\; у,\; z)\; \backslash \; sim\; (х\text{'},\; y\; \text{'},\; z\text{'})\}$⇔ ∃ c ≠ 0, такое что x '= c x, y' = c y и z '= c z. В соответствии с этим отношением эквивалентности пространство называется проективной плоскостью $P\; 2\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{P\}\; ^\; \{2\}\}$; точки, обозначенные как $(x:\; y:\; z)\; \{\backslash \; displaystyle\; (x:\; y:\; z)\}$, соответствуют линиям в трехмерном пространстве, которые проходят через начало координат. Обратите внимание, что точка $(0:\; 0:\; 0)\; \{\backslash \; displaystyle\; (0:\; 0:\; 0)\}$не существует в этом пространстве, поскольку для рисования линии в любом возможном направлении требуется хотя бы один x ', y' или z '≠ 0. Теперь заметьте, что почти все прямые проходят через любую заданную базовую плоскость, например, (X, Y, 1) -плоскость, в то время как прямые, точно параллельные этой плоскости, имеют координаты ( X, Y, 0), укажите направления однозначно, как «точки на бесконечности», которые используются в аффинной (X, Y) -плоскости, над которой она лежит.

В алгоритме используется только групповая структура эллиптической кривой над полем. Поскольку нам не обязательно нужно поле, конечное поле также будет обеспечивать групповую структуру на эллиптической кривой. Однако, учитывая ту же кривую и операцию над $(Z\; /\; n\; Z)\; /\; \sim \; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\})\; /\; \backslash \; sim\}$с n not простое число не дает группы. Метод эллиптической кривой использует случаи отказа закона сложения.

Теперь сформулируем алгоритм в проективных координатах. Тогда нейтральный элемент задается бесконечно удаленной точкой $(0:\; 1:\; 0)\; \{\backslash \; displaystyle\; (0:\; 1:\; 0)\}$. Пусть n - (положительное) целое число, и рассмотрим эллиптическую кривую (набор точек с некоторой структурой на ней) $E\; (Z\; /\; n\; Z)\; =\; \{(x:\; y:\; z)\; \in \; P\; 2\; |\; Y\; 2\; Z\; знак\; равно\; Икс\; 3\; +\; axz\; 2\; +\; bz\; 3\}\; \{\backslash \; Displaystyle\; E\; (\backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\})\; =\; \backslash \; \{(x:\; y:\; z)\; \backslash \; in\; \backslash \; mathbb\; \{P\}\; ^\; \{\; 2\}\; \backslash \; |\; \backslash \; y\; ^\; \{2\}\; z\; =\; x\; ^\; \{3\}\; +\; axz\; ^\; \{2\}\; +\; bz\; ^\; \{3\}\; \backslash \}\}$.

1. Выберите $x\; P,\; y\; P,\; a\; \in \; Z\; /\; n\; Z\; \{\backslash \; displaystyle\; x\_\; \{P\},\; y\_\; \{P\},\; a\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\}\}$с ≠ 0.
2. Вычислить $b\; =\; y\; P\; 2\; -\; x\; P\; 3\; -\; ax\; P\; \{\backslash \; displaystyle\; b\; =\; y\_\; \{P\}\; ^\; \{2\}\; -x\_\; \{P\}\; ^\; \{3\}\; -ax\_\; \{P\}\}$. Эллиптическая кривая E имеет тогда форму Вейерштрасса, заданную формулой $y\; 2\; =\; x\; 3\; +\; ax\; +\; b\; \{\backslash \; displaystyle\; y\; ^\; \{2\}\; =\; x\; ^\; \{3\}\; +\; ax\; +\; b\}$и с использованием проективных координат эллиптическая кривая задается однородным уравнением $ZY\; 2\; =\; X\; 3\; +\; a\; Z\; 2\; X\; +\; b\; Z\; 3\; \{\backslash \; displaystyle\; ZY\; ^\; \{2\}\; =\; X\; ^\; \{3\}\; +\; aZ\; ^\; \{2\}\; X\; +\; bZ\; ^\; \{3\}\}$. Он имеет точку $P\; =\; (x\; P:\; y\; P:\; 1)\; \{\backslash \; displaystyle\; P\; =\; (x\_\; \{P\}:\; y\_\; \{P\}:\; 1)\}$.
3. Выберите верхнюю границу $B\; \in \; Z\; \{\; \backslash \; displaystyle\; B\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\}$для этой эллиптической кривой. Примечание. Вы найдете множители p, только если порядок групп эллиптической кривой E превышает $Z\; /\; p\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; p\; \backslash \; mathbb\; \{Z\}\}$(обозначается $\#\; E\; (Z\; /\; p\; Z)\; \{\backslash \; displaystyle\; \backslash \; \#E\; (\backslash \; mathbb\; \{Z\}\; /\; p\; \backslash \; mathbb\; \{Z\})\}$) равно B-smooth, что означает, что все простые множители $\#\; E\; (Z\; /\; p\; Z)\; \{\backslash \; displaystyle\; \backslash \; \#E\; (\backslash \; mathbb\; \{Z\}\; /\; p\; \backslash \; mathbb\; \{Z\})\}$должны быть меньше или равно B.
4. Вычислить $k\; =\; lcm\; (1,\dots ,\; B)\; \{\backslash \; displaystyle\; k\; =\; \{\backslash \; rm\; \{lcm\}\}\; (1,\; \backslash \; dots,\; B)\}$.
5. Вычислить $k\; P:\; =\; P\; +\; P\; +\; \cdots \; +\; P\; \{\backslash \; displaystyle\; kP:\; =\; P\; +\; P\; +\; \backslash \; cdots\; +\; P\}$(k раз) в кольце $E\; (Z\; /\; n\; Z)\; \{\backslash \; Displaystyle\; E\; (\backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\})\}$. Обратите внимание, что если $\#\; E\; (Z\; /\; n\; Z)\; \{\backslash \; displaystyle\; \backslash \; \#E\; (\backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\})\}$является B-гладким, а n - простым ( и поэтому $Z\; /\; n\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\}\}$является полем), что $k\; P\; =\; (0:\; 1:\; 0)\; \{\; \backslash \; displaystyle\; kP\; =\; (0:\; 1:\; 0)\}$. Однако, если только $\#\; E\; (Z\; /\; p\; Z)\; \{\backslash \; displaystyle\; \backslash \; \#E\; (\backslash \; mathbb\; \{Z\}\; /\; p\; \backslash \; mathbb\; \{Z\})\}$является B-гладким для некоторого делителя p из n произведение может не быть (0: 1: 0), потому что сложение и умножение не определены, если n не является простым. В этом случае можно найти нетривиальный делитель.
6. Если нет, вернитесь к шагу 2. Если это произойдет, вы заметите это при упрощении произведения $k\; P.\; \{\backslash \; displaystyle\; kP.\}$

В пункте 5 сказано, что при определенных обстоятельствах может быть найден нетривиальный делитель. Как указано в статье Ленстры (Факторинг целых чисел с эллиптическими кривыми), для сложения требуется предположение $gcd\; (x\; 1\; -\; x\; 2,\; n)\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; gcd\; (x\_\; \{1\}\; -x\_\; \{2\},\; n)\; =\; 1\}$. Если $P,\; Q\; \{\backslash \; displaystyle\; P,\; Q\}$не являются $(0:\; 1:\; 0)\; \{\backslash \; displaystyle\; (0:\; 1:\; 0)\}$и отдельный (в остальном сложение работает аналогично, но немного отличается), тогда сложение работает следующим образом:

• Для вычисления: $R\; =\; P\; +\; Q;\; \{\backslash \; displaystyle\; R\; =\; P\; +\; Q;\}$$P\; =\; (x\; 1:\; y\; 1:\; 1),\; Q\; =\; (x\; 2:\; y\; 2:\; 1)\; \{\backslash \; displaystyle\; P\; =\; (x\_\; \{1\}:\; y\_\; \{1)\; \}:\; 1),\; Q\; =\; (x\_\; \{2\}:\; y\_\; \{2\}:\; 1)\}$,
• $\lambda \; =\; (y\; 1\; -\; y\; 2)\; (x\; 1\; -\; x\; 2)\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; lambda\; =\; (y\_\; \{1\}\; -y\_\; \{2\})\; (x\_\; \{1\}\; -x\_\; \{2\})\; ^\; \{-\; 1\}\}$,
• $x\; 3\; =\; \lambda \; 2\; -\; x\; 1\; -\; x\; 2\; \{\backslash \; displaystyle\; x\_\; \{3\}\; =\; \backslash \; lambda\; ^\; \{2\}\; -x\_\; \{1\}\; -x\_\; \{2\}\}$,
• $y\; 3\; =\; \lambda \; (x\; 1\; -\; x\; 3)\; -\; y\; 1\; \{\backslash \; displaystyle\; y\_\; \{3\}\; =\; \backslash \; lambda\; (x\_\; \{1\}\; -x\_\; \{\; 3\})\; -\; y\_\; \{1\}\}$,
• $R\; =\; P\; +\; Q\; =\; (x\; 3:\; y\; 3:\; 1)\; \{\backslash \; displaystyle\; R\; =\; P\; +\; Q\; =\; (x\_\; \{3\}:\; y\_\; \{3\}:\; 1)\}$.

Если сложение не удалось, это произойдет из-за ошибки при вычислении $\lambda .\; \{\backslash \; displaystyle\; \backslash \; lambda.\}$В частности, потому что $(x\; 1\; -\; x\; 2)\; -\; 1\; \{\backslash \; displaystyle\; (x\_\; \{1\}\; -x\_\; \{2\})\; ^\; \{-\; 1\}\}$не всегда может быть вычислено, если n не является простым (и поэтому $Z\; /\; n\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\}\}$не является поле). Без использования поля $Z\; /\; n\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; n\; \backslash \; mathbb\; \{Z\}\}$можно вычислить:

• $\lambda \; \prime \; =\; y\; 1\; -\; y\; 2\; \{\backslash \; displaystyle\; \backslash \; lambda\; \text{'}=\; y\_\; \{1\}\; -y\_\; \{2\}\}$,
• $x\; 3\; \prime \; =\; \lambda \; \prime \; 2\; -\; x\; 1\; (x\; 1\; -\; x\; 2)\; 2\; -\; x\; 2\; (x\; 1\; -\; x\; 2)\; 2\; \{\backslash \; displaystyle\; x\_\; \{3\}\; \text{'}=\; \{\backslash \; lambda\text{'}\}\; ^\; \{2\}\; -x\_\; \{1\}\; (x\_\; \{1\}\; -x\_\; \{2\})\; ^\; \{2\}\; -x\_\; \{2\}\; (x\_\; \{1\}\; -\; x\_\; \{2\})\; ^\; \{2\}\}$,
• $y\; 3\; \prime \; =\; \lambda \; \prime \; (x\; 1\; (x\; 1\; -\; x\; 2)\; 2\; -\; x\; 3\; \prime )\; -\; y\; 1\; (x\; 1\; -\; x\; 2)\; 3\; \{\backslash \; displaystyle\; y\_\; \{3\}\; \text{'}=\; \backslash \; lambda\text{'}\; (x\_\; \{1\}\; (x\_\; \{1\}\; -x\_\; \{2\})\; ^\; \{2\}\; -x\_\; \{3\}\; \text{'})\; -\; y\_\; \{1\}\; (x\_\; \{1\}\; -x\_\; \{2\})\; ^\; \{3\}\}$,
• $R\; =\; P\; +\; Q\; =\; (x\; 3\; \prime \; (x\; 1\; -\; x\; 2):\; y\; 3\; \prime :\; (x\; 1\; -\; x\; 2)\; 3)\; \{\backslash \; displaystyle\; R\; =\; P\; +\; Q\; =\; (\; x\_\; \{3\}\; \text{'}(x\_\; \{1\}\; -x\_\; \{2\}):\; y\_\; \{3\}\text{'}\; :(\; x\_\; \{1\}\; -x\_\; \{2\})\; ^\; \{3\})\}$, и упростить, если возможно.

Это вычисление всегда допустимо, и если НОД Z-координаты равен n (1 или n), то при неудачном упрощении обнаруживается нетривиальный делитель n.

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

Определение. Пусть $k\; \{\backslash \; displaystyle\; k\}$будет полем, в котором $2\; \ne \; 0\; \{\backslash \; displaystyle\; 2\; \backslash \; neq\; 0\}$, и пусть $a,\; d\; \in \; K\; \setminus \; \{0\}\; \{\backslash \; displaystyle\; a,\; d\; \backslash \; in\; k\; \backslash \; setminus\; \backslash \; \{0\; \backslash \}\}$с $a\; \ne \; d\; \{\backslash \; displaystyle\; a\; \backslash \; neq\; d\}$. Тогда скрученная кривая Эдвардса $E\; E,\; a,\; d\; \{\backslash \; displaystyle\; E\_\; \{E,\; a,\; d\}\}$задается как $a\; x\; 2\; +\; y\; 2\; =\; 1\; +\; d\; x\; 2\; y\; 2.\; \{\backslash \; displaystyle\; ax\; ^\; \{2\}\; +\; y\; ^\; \{2\}\; =\; 1\; +\; dx\; ^\; \{2\}\; y\; ^\; \{2\}.\}$Кривая Эдвардса - это скрученная кривая Эдвардса, в которой $a\; =\; 1\; \{\backslash \; displaystyle\; a\; =\; 1\}$.

Существует пять известных способов построения набора точек на кривой Эдвардса: набор аффинных точек, набор проективных точек, набор перевернутых точек, набор расширенных точек. и набор завершенных точек.

Набор аффинных точек задается следующим образом:

$\{(x,\; y)\; \in \; A\; 2:\; ax\; 2\; +\; y\; 2\; =\; 1\; +\; dx\; 2\; y\; 2\}\; \{\backslash \; displaystyle\; \backslash \; \{(x,\; y)\; \backslash \; in\; \backslash \; mathbb\; \{A\}\; ^\; \{2\}:\; ax\; ^\; \{2\}\; +\; y\; ^\; \{2\}\; =\; 1\; +\; dx\; ^\; \{2\}\; y\; ^\; \{2\}\; \backslash \}\}$.

Закон сложения задается формулой

$(e,\; f),\; (g,\; h)\; \mapsto \; (eh\; +\; fg\; 1\; +\; degfh,\; fh\; -\; aeg\; 1\; -\; degfh).\; \{\backslash \; displaystyle\; (е,\; f),\; (g,\; h)\; \backslash \; mapsto\; \backslash \; left\; (\{\backslash \; frac\; \{eh\; +\; fg\}\; \{1\; +\; degfh\}\},\; \{\backslash \; frac\; \{fh-aeg\}\; \{1-degfh\}\}\; \backslash \; right).\}$

Точка (0,1) является ее нейтральным элементом, а обратная величина $(e,\; f)\; \{\backslash \; displaystyle\; (e,\; f)\}$равна $(-\; e,\; f)\; \{\backslash \; displaystyle\; (-e,\; f)\}$.

Другие представления определяются аналогично тому, как проективная кривая Вейерштрасса следует из аффинности.

Любая эллиптическая кривая в форме Эдвардса имеет точку порядка 4. Итак, торсионная группа кривой Эдвардса над $Q\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{\; Q\}\}$изоморфен либо $Z\; /\; 4\; Z,\; Z\; /\; 8\; Z,\; Z\; /\; 12\; Z,\; Z\; /\; 2\; Z\; \times \; Z\; /\; 4\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 4\; \backslash \; mathbb\; \{Z\},\; \backslash \; mathbb\; \{Z\}\; /\; 8\; \backslash \; mathbb\; \{Z\},\; \backslash \; mathbb\; \{Z\}\; /\; 12\; \backslash \; mathbb\; \{Z\},\; \backslash \; mathbb\; \{Z\}\; /\; 2\; \backslash \; mathbb\; \{Z\}\; \backslash \; times\; \backslash \; mathbb\; \{Z\; \}\; /\; 4\; \backslash \; mathbb\; \{Z\}\}$или $Z\; /\; 2\; Z\; \times \; Z\; /\; 8\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 2\; \backslash \; mathbb\; \{Z\}\; \backslash \; times\; \backslash \; mathbb\; \{Z\}\; /\; 8\; \backslash \; mathbb\; \{Z\}\}$.

Наиболее интересными случаями для ECM являются $Z\; /\; 12\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 12\; \backslash \; mathbb\; \{Z\}\}$и $Z\; /\; 2\; Z\; \times \; Z\; /\; 8\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 2\; \backslash \; mathbb\; \{Z\}\; \backslash \; times\; \backslash \; mathbb\; \{Z\}\; /\; 8\; \backslash \; mathbb\; \{Z\}\}$, поскольку они заставляют групповые порядки кривой по модулю простых чисел делятся на 12 и 16 соответственно. Следующие кривые имеют торсионную группу, изоморфную $Z\; /\; 12\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 12\; \backslash \; mathbb\; \{Z\}\}$:

• $x\; 2\; +\; y\; 2\; =\; 1\; +\; dx\; 2\; y\; 2\; \{\backslash \; displaystyle\; x\; ^\; \{2\}\; +\; y\; ^\; \{2\}\; =\; 1\; +\; dx\; ^\; \{2\}\; y\; ^\; \{2\}\}$с точкой $(a,\; b)\; \{\backslash \; displaystyle\; (a,\; b)\}$где $b\; \notin \; \{-\; 2,\; -\; 1/2,\; 0,\; \pm \; 1\},\; a\; 2\; =\; -\; (b\; 2\; +\; 2\; b)\; \{\backslash \; displaystyle\; b\; \backslash \; notin\; \backslash \; \{-\; 2,\; -\; 1\; /\; 2,0,\; \backslash \; pm\; 1\; \backslash \},\; a\; ^\; \{2\}\; =\; -\; (b\; ^\; \{2\}\; +\; 2b)\}$и $d\; =\; -\; (2\; b\; +\; 1)\; /\; (\; a\; 2\; b\; 2)\; \{\backslash \; displaystyle\; d\; =\; -\; (2b\; +\; 1)\; /\; (a\; ^\; \{2\}\; b\; ^\; \{2\})\}$
• $x\; 2\; +\; y\; 2\; =\; 1\; +\; dx\; 2\; y\; 2\; \{\backslash \; displaystyle\; x\; ^\; \{2\}\; +\; y\; ^\; \{2\}\; =\; 1\; +\; dx\; ^\; \{2\}\; y\; ^\; \{2\}\}$с точкой $(a,\; b)\; \{\backslash \; displaystyle\; (a,\; b)\}$где $a\; =\; u\; 2\; -\; 1\; u\; 2\; +\; 1,\; b\; =\; -\; (u\; -\; 1)\; 2\; u\; 2\; +\; 1\; \{\backslash \; displaystyle\; a\; =\; \{\backslash \; frac\; \{u\; ^\; \{2\}\; -1\}\; \{\; u\; ^\; \{2\}\; +1\}\},\; b\; =\; -\; \{\backslash \; frac\; \{(u-1)\; ^\; \{2\}\}\; \{u\; ^\; \{2\}\; +1\}\}\}$и $d\; =\; (u\; 2\; +\; 1)\; 3\; (u\; 2\; -\; 4\; u\; +\; 1)\; (u\; -\; 1)\; 6\; (u\; +\; 1)\; 2,\; u\; \notin \; \{0,\; \pm \; 1\}.\; \{\backslash \; displaystyle\; d\; =\; \{\backslash \; frac\; \{(u\; ^\; \{2\}\; +1)\; ^\; \{3\}\; (u\; ^\; \{2\}\; -4u\; +\; 1)\}\; \{(u-1)\; ^\; \{6\}\; (u\; +\; 1)\; ^\; \{2\}\}\},\; u\; \backslash \; notin\; \backslash \; \{0,\; \backslash \; pm\; 1\; \backslash \}.\}$

Каждую кривую Эдвардса с точкой порядка 3 можно записать способами, показанными выше. Кривые с торсионной группой, изоморфной $Z\; /\; 2\; Z\; \times \; Z\; /\; 8\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 2\; \backslash \; mathbb\; \{Z\}\; \backslash \; times\; \backslash \; mathbb\; \{Z\}\; /\; 8\; \backslash \; mathbb\; \{Z\}\}$и $Z\; /\; 2\; Z\; \times \; Z\; /\; 4\; Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; /\; 2\; \backslash \; mathbb\; \{Z\}\; \backslash \; times\; \backslash \; mathbb\; \{Z\}\; /\; 4\; \backslash \; mathbb\; \{Z\}\}$может быть более эффективным при поиске простых чисел.

Приведенный выше текст посвящен первому этапу факторизации эллиптической кривой. Там можно надеяться найти такой простой делитель p, что $s\; P\; \{\backslash \; displaystyle\; sP\}$является нейтральным элементом $E\; (Z\; /\; p\; Z)\; \{\backslash \; displaystyle\; E\; (\backslash \; mathbb\; \{\; Z\}\; /\; p\; \backslash \; mathbb\; \{Z\})\}$. На втором этапе можно надеяться найти такой простой делитель q, что $s\; P\; \{\backslash \; displaystyle\; sP\}$имеет малый порядок простых чисел в $E\; (Z\; /\; q\; Z)\; \{\backslash \; displaystyle\; E\; (\backslash \; mathbb\; \{Z\}\; /\; q\; \backslash \; mathbb\; \{Z\})\}$.

Мы надеемся, что порядок будет между $B\; 1\; \{\backslash \; displaystyle\; B\_\; \{1\}\}$и $B\; 2\; \{\backslash \; displaystyle\; B\_\; \{2\}\}$, где $B\; 1\; \{\backslash \; displaystyle\; B\_\; \{1\}\}$определяется на этапе 1, а $B\; 2\; \{\backslash \; displaystyle\; B\_\; \{2\}\}$- новый параметр этапа 2. Проверить наличие небольшого порядка $s\; P\; \{\backslash \; displaystyle\; sP\}$можно, вычислив $(ls)\; P\; \{\backslash \; displaystyle\; (ls)\; P\}$по модулю n для каждого простого l.

Использование эллиптических кривых Twisted Edwards, а также другие методы были использованы Бернштейном и др. Для обеспечения оптимизированной реализации ECM. Его единственный недостаток заключается в том, что он работает с меньшими составными числами, чем более универсальная реализация GMP-ECM Циммермана.

В последнее время появились разработки по использованию гиперэллиптических кривых для разложения целых чисел на множители. Косет показывает в своей статье (2010 г.), что можно построить гиперэллиптическую кривую с родом два (так что кривая $y\; 2\; =\; f\; (x)\; \{\backslash \; displaystyle\; y\; ^\; \{2\}\; =\; f\; (x)\}$с f степени 5), что дает тот же результат, что и при одновременном использовании двух "нормальных" эллиптических кривых. Использование поверхности Куммера делает расчет более эффективным. Недостатки гиперэллиптической кривой (по сравнению с эллиптической кривой) компенсируются этим альтернативным способом расчета. Поэтому Коссет грубо утверждает, что использование гиперэллиптических кривых для факторизации не хуже, чем использование эллиптических кривых.

Бернштейн, Хенингер, Лу и Валента предлагают GEECM, квантовую версию ECM с кривыми Эдвардса. Он использует алгоритм Гровера, чтобы примерно удвоить размер найденных простых чисел по сравнению со стандартным EECM, предполагая, что квантовый компьютер с достаточно большим количеством кубитов и скоростью, сравнимой с классическим компьютером, на котором работает EECM.

• UBASIC для практической программы (ECMX).

• Bernstein, Daniel J.; Биркнер, Питер; Ланге, Таня; Питерс, Кристиана (2013). «ECM с использованием кривых Эдвардса». Математика вычислений. 82 (282): 1139–1179. doi : 10.1090 / S0025-5718-2012-02633-0. MR 3008853.
• Bosma, W.; Хюльст, М. П. М. ван дер (1990). Доказательство первичности с помощью циклотомии. Кандидат наук. Диссертация, Universiteit van Amsterdam. OCLC 256778332.
• Брент, Ричард П. (1999). «Факторизация десятого числа Ферма». Математика вычислений. 68 (225): 429–451. doi : 10.1090 / S0025-5718-99-00992-8. MR 1489968.
• Коэн, Генри (1993). Курс вычислительной алгебраической теории чисел. Тексты для выпускников по математике. 138 . Берлин: Springer-Verlag. DOI : 10.1007 / 978-3-662-02945-9. ISBN 978-0-387-55640-6. MR 1228206.
• Косет, Р. (2010). «Факторизация с кривыми рода 2». Математика вычислений. 79 (270): 1191–1208. arXiv : 0905.2325. Bibcode : 2010MaCom..79.1191C. doi : 10.1090 / S0025-5718-09-02295-9. MR 2600562.
• Ленстра, А.К. ; Ленстра младший, Х. У., ред. (1993). Развитие сита числового поля. Конспект лекций по математике. 1554 . Берлин: Springer-Verlag. doi : 10.1007 / BFb0091534. ISBN 978-3-540-57013-4. MR 1321216.
• Ленстра-младший, Х. У. (1987). «Факторинг целых чисел с эллиптическими кривыми» (PDF). Анналы математики. 126 (3): 649–673. DOI : 10.2307 / 1971363. JSTOR 1971363. MR 0916721.
• Померанс, Карл ; Крэндалл, Ричард (2005). Простые числа: вычислительная перспектива (второе изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-25282-7. MR 2156291.
• Померанс, Карл (1985). «Алгоритм факторинга квадратного сита». Достижения в криптологии, Proc. Еврокрипт '84. Конспект лекций по информатике. 209 . Берлин: Springer-Verlag. С. 169–182. DOI : 10.1007 / 3-540-39757-4_17. ISBN 978-3-540-16076-2. MR 0825590.
• Померанс, Карл (1996). «Повесть о двух решетах» (PDF ). Уведомления Американского математического общества. 43(12): 1473–1485. MR 1416721.
• Сильверман, Роберт Д. (1987). «Квадратичное сито с множественными полиномами». Вычислительная математика. 48(177): 329–339. doi : 10.1090 / S0025-5718-1987-0866119-8. MR 0866119.
• Трапп, Вт.; Вашингтон, Л. С. (2006). Введение в криптографию с теорией кодирования (второе изд.). Сэдл-Ривер, штат Нью-Джерси: Pearson Prentice Hall. ISBN 978-0-13-186239-5. MR 2372272.
• Сэмюэл С. Вагстафф младший (2013). Радость факторинга. Провиденс, Род-Айленд: Американское математическое общество. С. 173–190. ISBN 978-1-4704-1048-3.
• Ватрас, Марчин (2008). Криптография, числовой анализ и очень большие числа. Быдгощ: Войцеховский-Штайнхаген. PL: 5324564.

• Факторизация с использованием метода эллиптических кривых, Java-апплета, который использует ECM и переключается на самоинициализирующееся квадратичное сито, когда он работает быстрее.
• GMP-ECM, эффективная реализация ECM.
• ECMNet, простая реализация клиент-сервер, которая работает с несколькими проектами факторизации.
• pyecm, реализация ECM на языке Python. Гораздо быстрее с psyco и / или gmpy.
• Проект распределенных вычислений yoyo @ Home Подпроект ECM - это программа для факторизации эллиптических кривых, которая используется несколькими проектами для поиска факторов для различных типов чисел.
• Исходный код алгоритма факторизации эллиптической кривой Ленстры Исходный код алгоритма факторизации эллиптической кривой Simple C и GMP.
• EECM-MPFQ Реализация ECM с использованием кривых Эдвардса, написанных с помощью библиотеки конечных полей MPFQ.