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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Декабрь 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Алгоритм [ править ]

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

1. Выберите случайную эллиптическую кривую над , с уравнением вида вместе с нетривиальной точки на ней.${\ Displaystyle \ mathbb {Z} / п \ 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. Вычислить на эллиптической кривой ( ), где - произведение множества малых чисел: скажем, произведение маленьких простых чисел в малых степенях, как в алгоритме p-1 , или факториал для некоторых не слишком больших чисел . Это можно сделать эффективно, по одному небольшому фактору за раз. Скажем, чтобы получить , сначала вычислить , потом , потом и так далее. выбирается так, чтобы быть достаточно маленьким, чтобы можно было выполнить поэлементное сложение точек в разумные сроки.${\displaystyle [k]P}$${\displaystyle {\bmod {n}}}$${\displaystyle k}$ ${\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}}}$
   • Если мы встречаем a, мы сделали: это нетривиальный фактор .${\displaystyle \gcd(v,n)\neq 1,m}$${\displaystyle n}$

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

Почему алгоритм работает? [ редактировать ]

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

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

ЕСМ получает вокруг этого препятствия, рассматривая группу случайной эллиптической кривой над конечным полем Z _р , а не учитывая мультипликативная группа из Z _р , которое всегда имеет порядок  р  - 1.

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

Пример [ править ]

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

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

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

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

Затем мы вычисляем 3 (2 P ). У нас есть s (2 P ) = 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. Следовательно, НОД (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^-1 = 81707 (мод 455839) и -593/106 = -133317 (мод 455839). Зная это s , мы можем вычислить координаты 2 (2 P ), как мы делали выше: 4 P = (259851, 116255). Просто чтобы убедиться, что это действительно точка на кривой: y ² = 54514 = x ³ + 5 x - 5 (mod 455839). После этого мы можем вычислить.${\displaystyle 3(2P)=4P\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), следовательно, повторное сложение здесь прервалось, что привело к факторизации.

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

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

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

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

Если сложение не удается, это будет из-за сбоя вычисления, в частности, потому что не всегда может быть вычислено, если n не является простым (и, следовательно , не является полем). Не используя поле, можно вычислить:${\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- координаты равен n (1 или n ), то при неудачном упрощении обнаруживается нетривиальный делитель n .

Скрученные кривые Эдвардса [ править ]

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

Определение. Пусть будет поле, в котором , и пусть с . Тогда скрученная кривая Эдвардса задается кривой Эдвардса. Кривая Эдвардса - это скрученная кривая Эдвардса, в которой .${\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) является нейтральным элементом и обратным IS .${\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 являются и , поскольку они заставляют групповые порядки кривой по модулю простых чисел делиться на 12 и 16 соответственно. Следующие кривые имеют группу кручения, изоморфную :${\displaystyle \mathbb {Z} /12\mathbb {Z} }$${\displaystyle \mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z} }$${\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 можно записать способами, показанными выше. Кривые с торсионной группой, изоморфной и могут быть более эффективными при нахождении простых чисел. ^[2]${\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 [ править ]

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

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

GMP-ECM и EECM-MPFQ [ править ]

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

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

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

Квантовая версия (GEECM) [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

• Бернштейн, Даниэль Дж .; Биркнер, Питер; Ланге, Таня; Питерс, Кристиана (2013). «ECM с использованием кривых Эдвардса». Математика вычислений . 82 (282): 1139–1179. DOI : 10.1090 / S0025-5718-2012-02633-0 . Руководство по ремонту  3008853 .
• Bosma, W .; Хульст, МПМ ван дер (1990). Доказательство первичности с помощью циклотомии . Кандидат наук. Диссертация, Universiteit van Amsterdam. OCLC  256778332 .
• Брент, Ричард П. (1999). «Факторизация десятого числа Ферма» . Математика вычислений . 68 (225): 429–451. DOI : 10.1090 / S0025-5718-99-00992-8 . Руководство по ремонту  1489968 .
• Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Тексты для выпускников по математике. 138 . Берлин: Springer-Verlag. DOI : 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 . DOI : 10.1090 / S0025-5718-09-02295-9 . Руководство по ремонту  2600562 .
• Ленстра, АК ; Ленстра младший, HW, ред. (1993). Развитие сита числового поля . Конспект лекций по математике. 1554 . Берлин: Springer-Verlag. DOI : 10.1007 / BFb0091534 . ISBN 978-3-540-57013-4. Руководство по ремонту  1321216 .
• Ленстра младший, HW (1987). «Факторинг целых чисел с эллиптическими кривыми» (PDF) . Анналы математики . 126 (3): 649–673. DOI : 10.2307 / 1971363 . JSTOR  1971363 . Руководство по ремонту  0916721 .
• Померанс, Карл ; Крэндалл, Ричард (2005). Простые числа: вычислительная перспектива (второе изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-25282-7. Руководство по ремонту  2156291 .
• Померанс, Карл (1985). «Алгоритм факторинга квадратного сита». Достижения в криптологии, Proc. Еврокрипт '84 . Конспект лекций по информатике. 209 . Берлин: Springer-Verlag. С. 169–182. DOI : 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. DOI : 10.1090 / S0025-5718-1987-0866119-8 . Руководство по ремонту  0866119 .
• Трапп, Вт .; Вашингтон, LC (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 , простая реализация клиент-сервер, работающая с несколькими проектами факторизации.
• pyecm , реализация ECM на языке Python. Намного быстрее с psyco и / или gmpy.
• Проект распределенных вычислений yoyo @ Home Subproject ECM - это программа для факторизации эллиптических кривых, которая используется в нескольких проектах для поиска факторов для различных типов чисел.
• Исходный код алгоритма факторизации эллиптической кривой Ленстры Исходный код простого алгоритма факторизации эллиптической кривой C и GMP.
• EECM-MPFQ Реализация ECM с использованием кривых Эдвардса, написанных с помощью библиотеки конечных полей MPFQ.