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

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

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

Алгоритм

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

1. случайную эллиптическую кривую Выберите $\mathbb {Z} /n\mathbb {Z}$ (целые числа по модулю $n$), с уравнением вида $y^{2}=x^{3}+ax+b{\pmod {n}}$ вместе с нетривиальной точкой $P(x_{0},y_{0})$ на этом.

   Это можно сделать, сначала выбрав случайный $x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z}$, а затем установка $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}$ чтобы убедиться, что точка находится на кривой.

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

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

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

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

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

Объяснение

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

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

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

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

Пример использования

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

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

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

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

Затем мы вычисляем 3(2 P ). Имеем 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(2 P ), как мы это делали выше: 4 P = (259851, 116255). Просто чтобы убедиться, что это действительно точка на кривой: y ² = 54514 = х ³ + 5 х – 5 (мод. 455839). После этого мы можем вычислить $3(2P)=4P\boxplus 2P$.

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

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

Алгоритм с проективными координатами

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

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

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

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

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

• Для расчета: $R=P+Q;$ $P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)$,
• $\lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}$,
• $x_{3}=\lambda ^{2}-x_{1}-x_{2}$,
• $y_{3}=\lambda (x_{1}-x_{3})-y_{1}$,
• $R=P+Q=(x_{3}:y_{3}:1)$.

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

• $\lambda '=y_{1}-y_{2}$,
• $x_{3}'={\lambda '}^{2}-x_{1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}$,
• $y_{3}'=\lambda '(x_{1}(x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}$,
• $R=P+Q=(x_{3}'(x_{1}-x_{2}):y_{3}':(x_{1}-x_{2})^{3})$и, если возможно, упростите.

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

Искривленные кривые Эдвардса

Основная статья: Искривленная кривая Эдвардса

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

Определение. Позволять $k$ быть областью, в которой $2\neq 0$, и пусть $a,d\in k\setminus \{0\}$ с $a\neq d$. Тогда искривленная кривая Эдвардса $E_{E,a,d}$ дается $ax^{2}+y^{2}=1+dx^{2}y^{2}.$ Кривая Эдвардса — это скрученная кривая Эдвардса, в которой $a=1$.

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

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

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

Закон сложения имеет вид

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

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

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

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

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

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

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

Этап 2

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

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

GMP-ECM и EECM-MPFQ

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

Метод гиперэллиптических кривых (HECM)

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

Квантовая версия (GEECM)

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

Ссылки

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

Внешние ссылки

• Факторизация с использованием метода эллиптической кривой — приложения WebAssembly, которое использует ECM и переключается на самоинициализирующееся квадратичное решето, когда оно работает быстрее.
• GMP-ECM. Архивировано 12 сентября 2009 г. на Wayback Machine . Это эффективная реализация ECM.
• ECMNet — простая реализация клиент-сервера, которая работает с несколькими проектами факторизации.
• pyecm — реализация ECM на Python.
• Проект распределенных вычислений yoyo@Home Subproject ECM — это программа факторизации эллиптических кривых, которая используется для поиска множителей для различных типов чисел.
• Исходный код алгоритма факторизации эллиптических кривых Lenstra Исходный код простого алгоритма факторизации эллиптических кривых C и GMP.
• EECM-MPFQ Реализация ECM с использованием кривых Эдвардса, написанных с помощью библиотеки конечных полей MPFQ.