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

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

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

Алгоритм

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

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

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

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

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

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

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

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

Почему алгоритм работает?

Если п и q два простых делителя п, тогда у² = Икс³ + топор + б (модп) следует то же уравнение также по модулюп и по модулюq. Эти две меньшие эллиптические кривые с ${\displaystyle \boxplus }$-дополнение теперь подлинное группы. Если эти группы имеют N_п и N_q элементов соответственно, то для любой точки п на исходной кривой по Теорема Лагранжа, k > 0 минимален такой, что ${\displaystyle kP=\infty }$ на кривой по модулю п подразумевает, что k разделяет N_п; более того, ${\displaystyle N_{p}P=\infty }$. Аналогичное утверждение верно для кривой по модулю q. Когда эллиптическая кривая выбирается случайным образом, то N_п и N_q случайные числа, близкие к п + 1 и q + 1, соответственно (см. ниже). Следовательно, маловероятно, что большинство основных факторов N_п и N_q одинаковы, и вполне вероятно, что при вычислении eP, мы встретим некоторые кП то есть ∞ по модулюп но нет по модулюq, или наоборот. В этом случае кП не существует на исходной кривой, и в ходе вычислений мы обнаружили некоторые v либо с gcd (v,п) = п или gcd (v, q) = q, но не то и другое. Это, gcd (v, п) дал нетривиальный фактор изп.

ECM по своей сути является улучшением более старых п − 1 алгоритм. В п − 1 алгоритм находит простые множители п такой, что п − 1 является b-powersmooth для малых значений б. Для любого е, кратное п − 1, и любой а относительно простой к п, от Маленькая теорема Ферма у нас есть а^е ≡ 1 (мод п). потом gcd (а^е − 1, п) может произвести фактор п. Однако алгоритм не работает, когда п - 1 имеет большие простые множители, как и в случае чисел, содержащих сильные простые числа, Например.

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

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

Пример

Следующий пример взят из Трапп и Вашингтон (2006), с добавлением некоторых деталей.

Мы хотим учитывать п = 455839. Выберем эллиптическую кривую у² = Икс³ + 5Икс – 5, с точкой п = (1, 1) на нем, и давайте попробуем вычислить (10!)п.

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

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

Затем вычисляем 3 (2п). У нас есть s(2п) = s(14, -53) = –593/106 (мод. п). С использованием Евклидов алгоритм: 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п), как и выше: 4п = (259851, 116255). Просто чтобы убедиться, что это действительно точка на кривой: у² = 54514 = Икс³ + 5Икс - 5 (обр. 455839). После этого мы можем вычислить ${\displaystyle 3(2P)=4P\boxplus 2P}$.

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

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

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

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

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

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

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

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

• Вычислять: ${\displaystyle R=P+Q;}$ ${\displaystyle P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)}$,
• ${\displaystyle \lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}}$,
• ${\displaystyle x_{3}=\lambda ^{2}-x_{1}-x_{2}}$,
• ${\displaystyle y_{3}=\lambda (x_{1}-x_{3})-y_{1}}$,
• ${\displaystyle R=P+Q=(x_{3}:y_{3}:1)}$.

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

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

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

Скрученные кривые Эдвардса

Основная статья: Скрученная кривая Эдвардса

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

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

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

Набор аффинных точек определяется выражением:

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

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

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

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

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

Любые эллиптическая кривая в форме Эдвардса - вопрос по порядку ведения заседания 4. Итак, торсионная группа кривой Эдвардса над ${\displaystyle \mathbb {Q} }$ изоморфен либо ${\displaystyle \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} }$ или ${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$.

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

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

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

2 этап

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

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

GMP-ECM и EECM-MPFQ

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

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

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

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

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

Смотрите также

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

использованная литература

1. 50 важнейших факторов, обнаруженных ECM.
2. Berstein, Daniel J .; Биркнер, Питер; Ланге, Таня; Питерс, Кристиана (9 января 2008 г.). «ECM с использованием кривых Эдвардса» (PDF). Криптология ePrint Archive. (примеры таких кривых см. в верхней части страницы 30)
3. Бернштейн Д.Дж., Хенингер Н., Лу П., Валентина Л. (2017) Постквантовый RSA. В: Lange T., Takagi T. (ред.), Постквантовая криптография. PQCrypto 2017. Lecture Notes in Computer Science, vol 10346. Springer, Cham

• Бернштейн, Даниэль Дж .; Биркнер, Питер; Ланге, Таня; Питерс, Кристиана (2013). «ECM с использованием кривых Эдвардса». Математика вычислений. 82 (282): 1139–1179. Дои:10.1090 / S0025-5718-2012-02633-0. Г-Н  3008853.
• Bosma, W .; Хюльст, М. П. М. ван дер (1990). Доказательство первичности с помощью циклотомии. Кандидат наук. Диссертация, Universiteit van Amsterdam. OCLC  256778332.
• Брент, Ричард П. (1999). «Факторизация десятого числа Ферма». Математика вычислений. 68 (225): 429–451. Дои: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.
• Коссет, Р. (2010). «Факторизация с кривыми рода 2». Математика вычислений. 79 (270): 1191–1208. arXiv:0905.2325. Bibcode:2010MaCom..79.1191C. Дои:10.1090 / S0025-5718-09-02295-9. Г-Н  2600562.
• Ленстра, А.К.; Ленстра младший, Х. У., ред. (1993). Развитие сита числового поля. Конспект лекций по математике. 1554. Берлин: Springer-Verlag. Дои:10.1007 / BFb0091534. ISBN  978-3-540-57013-4. Г-Н  1321216.
• Ленстра-младший, Х. В. (1987). «Факторинг целых чисел с эллиптическими кривыми» (PDF). Анналы математики. 126 (3): 649–673. Дои:10.2307/1971363. JSTOR  1971363. Г-Н  0916721.
• Померанс, Карл; Крэндалл, Ричард (2005). Простые числа: вычислительная перспектива (Второе изд.). Нью-Йорк: Спрингер. ISBN  978-0-387-25282-7. Г-Н  2156291.
• Померанс, Карл (1985). «Алгоритм факторинга квадратного сита». Достижения в криптологии, Proc. Еврокрипт '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). Криптография, числовой анализ и очень большие числа. Быдгощ: Войцеховский-Штайнхаген. PL: 5324564.

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

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