Jump to content

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

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

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

Алгоритм

[ редактировать ]

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

  1. случайную эллиптическую кривую Выберите (целые числа по модулю ), с уравнением вида вместе с нетривиальной точкой на этом.
    Это можно сделать, сначала выбрав случайный , а затем установка чтобы убедиться, что точка находится на кривой.
  2. Можно определить добавление двух точек на кривую, чтобы определить группу . Законы сложения приведены в статье об эллиптических кривых .
    Мы можем образовывать повторяющиеся кратные точки : . Формулы сложения включают в себя взятие модульного наклона соединения хорд. и и, таким образом, разделение между классами остатков по модулю , выполняемый с использованием расширенного алгоритма Евклида . В частности, деление на некоторые включает в себя расчет .
    Предполагая, что мы вычисляем наклон формы с , то если , результат сложения точек будет , точка «на бесконечности», соответствующая пересечению «вертикальной» линии, соединяющей и кривая. Однако, если , то добавление точек не приведет к созданию значимой точки на кривой; но, что более важно, является нетривиальным фактором .
  3. Вычислить на эллиптической кривой ( ), где является произведением многих малых чисел: скажем, произведением маленьких простых чисел, возведенных в малые степени, как в алгоритме p-1 , или факториалом для некоторых не слишком большой . Это можно сделать эффективно, по одному небольшому фактору за раз. Скажем, чтобы получить , сначала вычислить , затем , затем , и так далее. выбирается достаточно малым, чтобы -мудрое добавление точек может быть выполнено в разумные сроки.
    • Если мы закончим все приведенные выше расчеты, не встретив необратимых элементов ( ), это означает, что порядок эллиптических кривых (по модулю простых чисел) недостаточно гладкий , поэтому нам нужно попробовать еще раз с другой кривой и начальной точкой.
    • Если мы столкнемся с мы закончили: это нетривиальный фактор .

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

Объяснение

[ редактировать ]

Если p и q — два простых делителя n , то y 2 = х 3 + ax + b (mod n ) подразумевает то же уравнение также по модулю p и по модулю q . Эти две меньшие эллиптические кривые с -дополнение теперь являются подлинными группами . Если эти группы имеют N p и N q элементов соответственно, то для любой точки P на исходной кривой по Лагранжа теореме k > 0 минимально такое, что на кривой по модулю p следует, что k делит N p ; более того, . Аналогичное утверждение справедливо и для кривой по модулю 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 . дал

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 2 = х 3 + 5 x – 5, с точкой P = (1, 1) на ней, и попробуем вычислить (10!) P .

Наклон касательной в некоторой точке A =( x , y ) равен s = (3 x 2 + 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 – 2 x = 14 и y = s ( x x ) – y = 4(1 – 14) – 1 = –53, все числа понятны (по модулю n ). Просто чтобы проверить, что этот 2 P действительно находится на кривой: (–53) 2 = 2809 = 14 3 + 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 −1 = 81707 (мод. 455839) и –593/106 = –133317 (мод. 455839). Учитывая это s , мы можем вычислить координаты 2(2 P ), как мы это делали выше: 4 P = (259851, 116255). Просто чтобы убедиться, что это действительно точка на кривой: y 2 = 54514 = х 3 + 5 х – 5 (мод. 455839). После этого мы можем вычислить .

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

Причина, по которой это сработало, заключается в том, что кривая (mod 599) имеет 640 = 2. 7 ·5 очков, тогда как (по модулю 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 . В соответствии с этим отношением эквивалентности пространство называется проективной плоскостью. ; точки, обозначаемые , соответствуют линиям в трехмерном пространстве, проходящим через начало координат. Обратите внимание, что точка не существует в этом пространстве, поскольку для рисования линии в любом возможном направлении требуется хотя бы одно из x',y' или z' ≠ 0. Теперь заметим, что почти все линии проходят через любую заданную опорную плоскость - например ( X , Y ,1)-плоскость, в то время как линии, точно параллельные этой плоскости, имеющие координаты ( X,Y ,0), однозначно определяют направления, как «точки на бесконечности», которые используются в аффинной ( X,Y )-плоскости. лежит выше.

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

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

  1. Выбирать с 0.
  2. Рассчитать . Эллиптическая кривая E тогда имеет форму Вейерштрасса, заданную формулой а с использованием проективных координат эллиптическая кривая задается однородным уравнением . В этом есть смысл .
  3. Выберите верхнюю границу для этой эллиптической кривой. Примечание. Вы найдете факторы p только в том случае, если групповой порядок эллиптической кривой E по (обозначается ) является B-гладким , что означает, что все простые факторы должно быть меньше или равно B .
  4. Рассчитать .
  5. Рассчитать ( k раз) на ринге . Обратите внимание, что если является B -гладким и n простое (и, следовательно, это поле), что . Однако, если только является B-гладким для некоторого делителя p числа n , произведение может не быть (0:1:0), поскольку сложение и умножение не определены четко, если n не является простым. В этом случае можно найти нетривиальный делитель.
  6. Если нет, то вернитесь к шагу 2. Если это все-таки произошло, то вы это заметите при упрощении продукта.

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

  • Для расчета: ,
  • ,
  • ,
  • ,
  • .

Если сложение не удалось, это произойдет из-за сбоя при расчете В частности, потому что не всегда может быть вычислено, если n не является простым (и, следовательно, это не поле). Не воспользовавшись будучи полем, можно было бы вычислить:

  • ,
  • ,
  • ,
  • и, если возможно, упростите.

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

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

[ редактировать ]

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

Определение. Позволять быть областью, в которой , и пусть с . Тогда искривленная кривая Эдвардса дается Кривая Эдвардса — это скрученная кривая Эдвардса, в которой .

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

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

.

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

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

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

Любая эллиптическая кривая в форме Эдвардса имеет точку порядка 4. Таким образом, группа кручения кривой Эдвардса над изоморфен либо или .

Наиболее интересные случаи для ECM: и , поскольку они заставляют групповые порядки кривой по простому модулю делиться на 12 и 16 соответственно. Следующие кривые имеют периодическую группу, изоморфную :

  • с точкой где и
  • с точкой где и

Любую кривую Эдвардса с точкой третьего порядка можно записать способами, указанными выше. Кривые с периодической группой, изоморфной и может быть более эффективным при поиске простых чисел. [2]

Приведенный выше текст посвящен первому этапу факторизации эллиптических кривых. Там надеются найти простой делитель p такой, что является нейтральным элементом .На втором этапе надеются найти простой делитель q такой, что имеет малый простой порядок в .

Мы надеемся, что порядок будет между и , где определяется на этапе 1 и это новый параметр этапа 2.Проверяю небольшой заказ , можно сделать, вычислив по модулю n для каждого простого числа l .

GMP-ECM и EECM-MPFQ

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]

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

  1. ^ 50 крупнейших факторов, найденных ECM .
  2. ^ Перейти обратно: а б Берштейн, Дэниел Дж.; Биркнер, Питер; Ланге, Таня ; Петерс, Кристиана (9 января 2008 г.). «ECM с использованием кривых Эдвардса» (PDF) . Архив электронной печати по криптологии . (примеры таких кривых см. в начале стр. 30)
  3. ^ Бернштейн DJ, Хенингер Н., Лу П., Валента Л. (2017) Постквантовый RSA . В: Ланге Т., Такаги Т. (ред.), Постквантовая криптография . PQCrypto 2017. Конспекты лекций по информатике, том 10346. Спрингер, Чам.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 9ca3e88f160805234d3ddfda6ad1c4d5__1713297840
URL1:https://arc.ask3.ru/arc/aa/9c/d5/9ca3e88f160805234d3ddfda6ad1c4d5.html
Заголовок, (Title) документа по адресу, URL1:
Lenstra elliptic-curve factorization - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)