Факторизация эллиптической кривой Ленстры
Эта статья может быть слишком технической для понимания большинства читателей . ( декабрь 2020 г. ) |
или Факторизация эллиптической кривой Ленстры метод факторизации эллиптической кривой ( ECM ) — это быстрый субэкспоненциальный алгоритм факторизации целых чисел , в котором используются эллиптические кривые . Для факторинга общего назначения ECM является третьим по скорости известным методом факторинга. Второе по скорости — квадратичное решето с кратным полиномом , а самое быстрое — решето с общим числовым полем . Факторизация эллиптической кривой Ленстры названа в честь Хендрика Ленстры .
Практически говоря, ECM считается алгоритмом факторинга специального назначения, поскольку он наиболее подходит для поиска небольших факторов. В настоящее время [update], это по-прежнему лучший алгоритм для делителей, не превышающих 50–60 цифр , поскольку время его работы зависит от размера наименьшего множителя p, а не от размера числа n, подлежащего факторизации. Часто ECM используется для удаления небольших множителей из очень большого целого числа со многими множителями; если оставшееся целое число по-прежнему является составным, то оно имеет только большие делители и факторизуется с использованием методов общего назначения. Самый большой коэффициент, найденный с помощью ECM, имеет 83 десятичных знака и был обнаружен 7 сентября 2013 года Р. Проппером. [1] Увеличение количества тестируемых кривых повышает шансы найти фактор, но они не являются линейными с увеличением количества цифр.
Алгоритм
[ редактировать ]Метод факторизации эллиптической кривой Ленстры для нахождения фактора заданного натурального числа. работает следующим образом:
- случайную эллиптическую кривую Выберите (целые числа по модулю ), с уравнением вида вместе с нетривиальной точкой на этом.
- Это можно сделать, сначала выбрав случайный , а затем установка чтобы убедиться, что точка находится на кривой.
- Можно определить добавление двух точек на кривую, чтобы определить группу . Законы сложения приведены в статье об эллиптических кривых .
- Мы можем образовывать повторяющиеся кратные точки : . Формулы сложения включают в себя взятие модульного наклона соединения хорд. и и, таким образом, разделение между классами остатков по модулю , выполняемый с использованием расширенного алгоритма Евклида . В частности, деление на некоторые включает в себя расчет .
- Предполагая, что мы вычисляем наклон формы с , то если , результат сложения точек будет , точка «на бесконечности», соответствующая пересечению «вертикальной» линии, соединяющей и кривая. Однако, если , то добавление точек не приведет к созданию значимой точки на кривой; но, что более важно, является нетривиальным фактором .
- Вычислить на эллиптической кривой ( ), где является произведением многих малых чисел: скажем, произведением маленьких простых чисел, возведенных в малые степени, как в алгоритме 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 — (положительное) целое число и рассмотрим эллиптическую кривую (набор точек с некоторой структурой на ней). .
- Выбирать с ≠ 0.
- Рассчитать . Эллиптическая кривая E тогда имеет форму Вейерштрасса, заданную формулой а с использованием проективных координат эллиптическая кривая задается однородным уравнением . В этом есть смысл .
- Выберите верхнюю границу для этой эллиптической кривой. Примечание. Вы найдете факторы p только в том случае, если групповой порядок эллиптической кривой E по (обозначается ) является B-гладким , что означает, что все простые факторы должно быть меньше или равно B .
- Рассчитать .
- Рассчитать ( k раз) на ринге . Обратите внимание, что если является B -гладким и n простое (и, следовательно, это поле), что . Однако, если только является B-гладким для некоторого делителя p числа n , произведение может не быть (0:1:0), поскольку сложение и умножение не определены четко, если n не является простым. В этом случае можно найти нетривиальный делитель.
- Если нет, то вернитесь к шагу 2. Если это все-таки произошло, то вы это заметите при упрощении продукта.
В пункте 5 сказано, что при определенных обстоятельствах можно найти нетривиальный делитель. Как указано в статье Ленстры (Факторинг целых чисел с помощью эллиптических кривых), для сложения необходимо предположение . Если не являются и различимы (иначе сложение работает аналогично, но немного по-другому), то сложение работает следующим образом:
- Для расчета: ,
- ,
- ,
- ,
- .
Если сложение не удалось, это произойдет из-за сбоя при расчете В частности, потому что не всегда может быть вычислено, если n не является простым (и, следовательно, это не поле). Не воспользовавшись будучи полем, можно было бы вычислить:
- ,
- ,
- ,
- и, если возможно, упростите.
Это вычисление всегда допустимо, и если НОД Z -координаты с n ≠ (1 или n нетривиальный делитель n ), то при неудачном упрощении находится .
Искривленные кривые Эдвардса
[ редактировать ]Использование кривых Эдвардса требует меньшего количества модульных умножений и меньше времени, чем использование кривых Монтгомери или кривых Вейерштрасса (другие используемые методы). Используя кривые Эдвардса, вы также можете найти больше простых чисел.
Определение. Позволять быть областью, в которой , и пусть с . Тогда искривленная кривая Эдвардса дается Кривая Эдвардса — это скрученная кривая Эдвардса, в которой .
Известны пять способов построения набора точек на кривой Эдвардса: набор аффинных точек, набор проективных точек, набор инвертированных точек, набор расширенных точек и набор завершенных точек.
Набор аффинных точек определяется следующим образом:
- .
Закон сложения имеет вид
Точка (0,1) является ее нейтральным элементом и инверсией является .
Остальные представления определяются аналогично тому, как проективная кривая Вейерштрасса следует из аффинной.
Любая эллиптическая кривая в форме Эдвардса имеет точку порядка 4. Таким образом, группа кручения кривой Эдвардса над изоморфен либо или .
Наиболее интересные случаи для ECM: и , поскольку они заставляют групповые порядки кривой по простому модулю делиться на 12 и 16 соответственно. Следующие кривые имеют периодическую группу, изоморфную :
- с точкой где и
- с точкой где и
Любую кривую Эдвардса с точкой третьего порядка можно записать способами, указанными выше. Кривые с периодической группой, изоморфной и может быть более эффективным при поиске простых чисел. [2]
Этап 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.
Ссылки
[ редактировать ]- ^ 50 крупнейших факторов, найденных ECM .
- ^ Перейти обратно: а б Берштейн, Дэниел Дж.; Биркнер, Питер; Ланге, Таня ; Петерс, Кристиана (9 января 2008 г.). «ECM с использованием кривых Эдвардса» (PDF) . Архив электронной печати по криптологии . (примеры таких кривых см. в начале стр. 30)
- ^ Бернштейн DJ, Хенингер Н., Лу П., Валента Л. (2017) Постквантовый RSA . В: Ланге Т., Такаги Т. (ред.), Постквантовая криптография . PQCrypto 2017. Конспекты лекций по информатике, том 10346. Спрингер, Чам.
- Бернштейн, Дэниел Дж.; Биркнер, Питер; Ланге, Таня; Петерс, Кристиана (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. doi : 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. Исходный код алгоритма факторизации эллиптических кривых Lenstra. Исходный код простого C и GMP.
- EECM-MPFQ Реализация ECM с использованием кривых Эдвардса, написанных с помощью библиотеки конечных полей MPFQ.