Записи дискретного логарифма

Записи дискретного логарифма — это лучшие результаты, достигнутые на сегодняшний день при решении задачи дискретного логарифмирования , которая представляет собой задачу поиска решения x уравнения $g^{x}=h$ заданы элементы и h конечной циклической G группы . g Сложность этой проблемы лежит в основе безопасности нескольких криптографических систем, включая Диффи-Хеллмана соглашение о ключах , шифрование Эль-Гамаля , схему подписи Эль-Гамаля , алгоритм цифровой подписи и их аналоги в криптографии на основе эллиптических кривых . Обычный выбор G , используемый в этих алгоритмах, включает мультипликативную группу целых чисел по модулю p , мультипликативную группу конечного поля и группу точек на эллиптической кривой над конечным полем.

Электрический ток ^{[ нужно обновить ]} Рекорд целых чисел по модулю простых чисел , установленный в декабре 2019 года, представляет собой вычисление дискретного логарифма по модулю простого числа с 240 цифрами. Для характеристики 2 текущий рекорд для конечных полей, установленный в июле 2019 года, представляет собой дискретный логарифм по $\mathrm {GF} (2^{30750})$ . При ограничении простыми показателями ^{[ нужны разъяснения ]}, текущий рекорд, установленный в октябре 2014 года, уже позади. $\mathrm {GF} (2^{1279})$ . По признаку 3 текущий рекорд, установленный в июле 2016 года, преодолен. $\mathrm {GF} (3^{6*509})$ . Для полей расширения Куммера установлено значение «умеренный». ^{[ нужны разъяснения ]} характеристика, текущий рекорд, установленный в январе 2013 года, уже позади $\mathrm {GF} (33341353^{57})$ . Для полей «умеренной» характеристики (которые не обязательно являются расширениями Куммера) текущий рекорд, опубликованный в 2022 году, закончился. $\mathrm {GF} (2111023^{50})$ .

Целые числа по модулю p

2 декабря 2019 года Фабрис Будо, Пьеррик Годри, Аврора Гийевич, Надя Хенингер , Эммануэль Томе и Поль Циммерманн объявили о вычислении дискретного логарифма по модулю 240-значного (795 бит) простого числа RSA-240 + 49204 (первое безопасное простое число). выше RSA-240). Это вычисление выполнялось одновременно с факторизацией RSA-240 с использованием алгоритма сита числового поля и программного обеспечения CADO-NFS с открытым исходным кодом. Часть вычислений с дискретным логарифмом заняла около 3100 ядер-лет с использованием в качестве эталона процессоров Intel Xeon Gold 6130 (2,1 ГГц). По оценкам исследователей, улучшения в алгоритмах и программном обеспечении сделали эти вычисления в три раза быстрее, чем можно было бы ожидать от предыдущих записей с учетом усовершенствований в аппаратном обеспечении. ^[1]^[2]

Предыдущие записи для целых чисел по модулю p включают:

16 июня 2016 года Торстен Кляйнъюнг, Клаус Дьем, Арьен К. Ленстра , Кристина Приплата и Колин Штальке объявили о вычислении дискретного логарифма по модулю 232-значного (768-битного) безопасного простого числа с использованием сита числового поля. Вычисления были начаты в феврале 2015 года и заняли около 6600 ядерных лет при масштабировании до Intel Xeon E5-2660 с частотой 2,2 ГГц. ^[3]
18 июня 2005 года Антуан Жу и Рейнальд Лерсье объявили о вычислении дискретного логарифма по модулю 130-значного (431-битного) сильного простого числа за три недели с использованием 16-процессорного компьютера HP AlphaServer GS1280 с тактовой частотой 1,15 ГГц и сита числового поля. алгоритма . ^[4]
5 февраля 2007 года это было заменено объявлением Торстена Кляйнъунга о вычислении дискретного логарифма по модулю 160-значного (530-битного) безопасного простого числа, снова с использованием сита числового поля. Большая часть вычислений выполнялась во время простоя на различных ПК и в параллельном вычислительном кластере. ^[5]
11 июня 2014 года Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джельжели и Эммануэль Томе объявили о вычислении дискретного логарифма по модулю 180-значного (596-битного) безопасного простого числа с использованием алгоритма сита числового поля. ^[6]

Также следует отметить, что в июле 2016 года Джошуа Фрид, Пьеррик Годри, Надя Хенингер и Эммануэль Том опубликовали свои вычисления дискретного логарифма для 1024-битного простого числа. ^[7] Они сгенерировали простое число, восприимчивое к сетке специального числового поля, используя специализированный алгоритм на сравнительно небольшой подгруппе (160 бит). Хотя это небольшая подгруппа, это был стандартизированный размер подгруппы, используемый с 1024-битным алгоритмом цифровой подписи (DSA).

Дискретный логарифм записывает простые числа по модулю
Размер простого	Тип прайма	Дата объявления	Объявлено	Алгоритм	Аппаратное обеспечение	Примечания
240-значный (795-битный)	безопасный премьер	2 декабря 2019 г.	Фабрис Будо Пьеррик Годри Аврора Гилевич Надя Хенингер Эммануэль Томе Пол Циммерманн	сито числового поля		Использованное простое число было RSA-240 + 49204 (первое безопасное простое число выше RSA-240). Этот расчет проводился одновременно ^{[ как? ]} с факторизацией RSA-240 с использованием алгоритма Number Field Sieve и программного обеспечения CADO-NFS с открытым исходным кодом. Улучшения в алгоритмах и программном обеспечении ^{[ который? ]} сделал это вычисление примерно в три раза быстрее, чем можно было бы ожидать на основе предыдущих записей с учетом усовершенствований аппаратного обеспечения.
1024-битный		июль 2016 г.	Джошуа Фрид Пьеррик Годри Надя Хенингер Эммануэль Томе	сито с полем специального номера		Исследователи создали простой восприимчивый ^{[ почему? ]} в поле специального номера сито ^{[ как? ]} используя специализированный алгоритм ^{[ который? ]} на сравнительно небольшой подгруппе (160 бит).
232-значный (768-битный)	безопасный премьер	16 июня 2016 г.	Торстен Кляйнъунг Клаус Дьем Арьен К. Ленстра Кристина Приплата Колин Сталке	сито числового поля		Эти расчеты начались в феврале 2015 года.
180 цифр (596 бит)	безопасный премьер	11 июня 2014 г.	Сирил Бувье Пьеррик Годри Лоран Имбер Хамза Джелджели Эммануэль Томе	сито числового поля
160-значный (530-битный)	безопасный премьер	5 февраля 2007 г.	Торстен Кляйнъунг	сито числового поля	различные ПК, кластер параллельных вычислений ^{[ который? ]}
130-значный (431-битный)	сильный прайм	18 июня 2005 г.	Антуан Жу Рейнальд Лерсье	сито числового поля	16-процессорный процессор HP AlphaServer GS1280 с тактовой частотой 1,15 ГГц

Конечные поля

Текущий рекорд (по состоянию на июль 2019 г.) ^[update]) в конечном поле характеристики 2 было объявлено Робертом Грейнджером, Торстеном Кляйнъюнгом, Арьеном Ленстра, Бенджамином Весоловски и Йенсом Зумбрегелем 10 июля 2019 года. ^[8] Эта команда смогла вычислить дискретные логарифмы в GF(2 ³⁰⁷⁵⁰), используя 25 481 219 часов ядра в кластерах на базе архитектуры Intel Xeon. Это вычисление было первым крупномасштабным примером использования шага исключения квазиполиномиального алгоритма. ^[9]

Предыдущие рекорды в конечном поле характеристики 2 были анонсированы:

Роберт Грейнджер, Торстен Кляйнъунг и Йенс Зумбрегель, 31 января 2014 г. Эта команда смогла вычислить дискретные логарифмы в GF(2 ⁹²³⁴), используя около 400 000 основных часов. Новые особенности этого вычисления включают модифицированный метод получения логарифмов элементов второй степени и систематически оптимизированную стратегию спуска. ^[10]
Антуан Жу, 21 мая 2013 года. Его команда смогла вычислить дискретные логарифмы в полевых условиях с помощью 2 ⁶¹⁶⁸ = (2 ²⁵⁷) ²⁴ элементы, использующие менее 550 часов процессора. Это вычисление было выполнено с использованием того же алгоритма расчета индекса, что и в недавнем вычислении в поле с 2 ⁴⁰⁸⁰ элементы. ^[11]
Роберт Грейнджер, Фарук Гёлоглу, Гэри Макгуайр и Йенс Зумбрегель, 11 апреля 2013 г. Новые вычисления касались поля с 2 ⁶¹²⁰ элементов и заняло 749,5 основных часов.
Антуан Жу, 22 марта 2013 г. При этом использовался тот же алгоритм. ^[12] для малых характеристических полей, как и предыдущий расчет в поле с 2 ¹⁷⁷⁸ элементы. Новый расчет касался поля с 2 ⁴⁰⁸⁰ 255 степени с 2 элементы, представленные в виде расширения поля ¹⁶ элементы. Вычисления заняли менее 14100 основных часов. ^[13]
Роберт Грейнджер, Фарук Гёлоглу, Гэри Макгуайр и Йенс Зумбрегель, 19 февраля 2013 г. Они использовали новый вариант сита поля функции базового поля среднего размера для двоичных полей для вычисления дискретного логарифма в поле 2. ¹⁹⁷¹ элементы. Чтобы использовать базовое поле среднего размера, они представляли поле как расширение поля 2 степени 73. ²⁷ элементы. Вычисления заняли 3132 часа на кластере SGI Altix ICE 8200EX с использованием шестиядерных процессоров Intel (Westmere) Xeon E5650. ^[14]
Антуан Жу, 11 февраля 2013 г. При этом использовался новый алгоритм для малых характеристических полей. Расчеты касались поля размером 2 ¹⁷⁷⁸ элементы, представленные как расширение поля 127 степени с 2 ¹⁴ элементы. Вычисления заняли менее 220 основных часов. ^[15]

Текущий рекорд (по состоянию на 2014 г.) ^[update]) в конечном поле характеристики 2 простой степени было объявлено Торстеном Кляйнъюнгом 17 октября 2014 года. Расчет проводился в поле 2 ¹²⁷⁹ элементов и следовал по существу пути, намеченному для $\mathrm {GF} (2^{4\cdot 1223})$ в ^[16] с двумя основными исключениями: вычислениями линейной алгебры и фазой спуска. Общее время работы составило менее четырех основных лет. ^[17] Предыдущий рекорд в конечном поле характеристики 2 простой степени был анонсирован группой CARAMEL 6 апреля 2013 года. Они использовали сито функционального поля для вычисления дискретного логарифма в поле 2. ⁸⁰⁹ элементы. ^[18]

Текущий рекорд (по состоянию на июль 2016 г.) ^[update]) для поля характеристики 3 было анонсировано Гора Адж, Исаак Каналес-Мартинес, Нарели Крус-Кортес, Альфред Менезес, Томаз Оливейра, Франсиско Родригес-Энрикес и Луис Ривера-Самаррипа, 18 июля 2016 г. Расчет проводился в 4841-битном конечном поле с 3 ^6 · 509 элементов и выполнялся на нескольких компьютерах в CINVESTAV иУниверситет Ватерлоо . В общей сложности на вычисления было затрачено около 200 лет вычислительного времени. ^[19]

Анонсированы предыдущие рекорды в конечном поле характеристики 3:

в полной версии статьи Жу и Пьеро Asiacrypt 2014 (декабрь 2014 г.). ^[20] ДЛП решается в поле GF(3 ^5 · 479), которое представляет собой 3796-битное поле. В этой работе не использовались какие-либо «особые» аспекты этой области, такие как свойства Куммера или свойства искривленного Куммера. Общее вычисление заняло менее 8600 процессоро-часов.
Гора Адж, Альфред Менезес, Томаз Оливейра и Франсиско Родригес-Энрикес, 26 февраля 2014 г., обновляя предыдущее объявление от 27 января 2014 г. Вычисления решают DLP в 1551-битном поле GF(3 ^6 · 163), что занимает 1201 час процессора. ^[21]^[22]
в 2012 году совместной командой Fujitsu, NICT и Университета Кюсю, которая вычислила дискретный логарифм в поле 3 ^6 · 97 элементов и размером 923 бита, ^[23] используя вариант сита функционального поля и побив предыдущий рекорд в поле из 3 ^6 · 71 элементов и размером 676 бит с большим отрывом. ^[24]

По полям с характеристиками «умеренного» размера примечательные вычисления по состоянию на 2005 год включали поля размером 65 537. ²⁵ элементы (401 бит), объявленные 24 октября 2005 г., и в поле 370801. ³⁰ элементы (556 бит), анонсированные 9 ноября 2005 г. ^[25] Текущий рекорд (по состоянию на 2013 год) для конечного поля расширения Куммера с «умеренной» характеристикой был объявлен 6 января 2013 года. Команда использовала новый вариант сита функционального поля для среднего простого случая для вычисления дискретного логарифма в поле Куммера. поле расширения 33341353 ⁵⁷ элементы (1425-битное конечное поле). ^[26]^[27] Тот же метод использовался несколькими неделями ранее для вычисления дискретного логарифма в поле расширения Куммера 33553771. ⁴⁷ элементы (1175-битное конечное поле). ^[27]^[28] Текущий рекорд (по состоянию на 2022 год) для конечного поля «умеренной» характеристики (которое не обязательно является расширением Куммера) - это вычисление дискретного логарифма в поле 2111023. ⁵⁰ элементы (1051-битное конечное поле); ^[29] предыдущая запись ^[30] вычислений дискретного логарифма над такими полями пришлось на поля, имеющие 297079 ⁴⁰ элементы (728-битныйконечное поле) и 64373 ³⁷ элементы (592-битное конечное поле). Эти вычисления были выполнены с использованием новых идей для ускорения анализа функционального поля.

25 июня 2014 года Разван Барбулеску, Пьеррик Годри, Аврора Гильевич и Франсуа Морен объявили о новом вычислении дискретного логарифма в конечном поле, порядок которого имеет 160 цифр и является расширением простого поля степени 2. ^[31] В качестве алгоритма использовалось решето числового поля (NFS) с различными модификациями. Общее время вычислений было эквивалентно 68 дням на одном ядре ЦП (просеивание) и 30 часам на графическом процессоре (линейная алгебра).

Записи дискретного логарифма над конечными полями
Чар.	Размер поля	Дата объявления	Объявлено	Аппаратное обеспечение	Вычислить	Примечания
2	2 ³⁰⁷⁵⁰	10 июля 2019 г.	Роберт Грейнджер Торстен Кляйнъунг Арьен Ленстра Бенджамин Весоловский Йенс Зумбрегель	Intel Xeon Архитектура	25 481 219 основных часов	Это вычисление было первым крупномасштабным примером использования шага исключения квазиполиномиального алгоритма. ^{[ нужны разъяснения ]}
	2 ¹²⁷⁹	17 октября 2014 г.	Торстен Кляйнъунг		<4 основных года
	2 ⁹²³⁴	31 января 2014 г.	Роберт Грейнджер Торстен Кляйнъунг Йенс Зумбрегель		~400 000 основных часов	Новые особенности этого вычисления включают модифицированный метод получения логарифмов элементов второй степени и систематически оптимизированную стратегию спуска. ^{[ нужны разъяснения ]}
	2 ⁶¹⁶⁸	21 мая 2013 г.	Антуан Жу		<550 часов процессора ^{[ количественно ]}
	2 ⁶¹²⁰	11 апреля 2013 г.	Роберт Грейнджер Фарук Гёлоглу Гэри Макгуайр Йенс Зумбрегель		749,5 ядер-часов
	2 ⁸⁰⁹	6 апреля 2013 г.	группа «КАРАМЕЛЬ» ^{[ ВОЗ? ]}
	2 ⁴⁰⁸⁰	22 марта 2013 г.	Антуан Жу		<14 100 основных часов ^{[ количественно ]}
	2 ¹⁹⁷¹	19 февраля 2013 г.	Роберт Грейнджер Фарук Гёлоглу Гэри Макгуайр Йенс Зумбрегель	Кластер SGI Altix ICE 8200EX Шестиядерные процессоры Intel (Westmere) Xeon E5650	3132 основных часа
	2 ¹⁷⁷⁸	11 февраля 2013 г.	Антуан Жу		<220 основных часов ^{[ количественно ]}
3	3 ^6 · 509	18 июля 2016 г.	Гора Адж Исаак Каналес-Мартинес Нарели Крус-Кортес Альфред Менезес Томаз Оливейра Франсиско Родригес-Энрикес Луис Ривера-Самаррипа	несколько компьютеров ^{[ который? ]} в CINVESTAV и Университете Ватерлоо	~200 основных лет
	3 ^5 · 479	декабрь 2014 г.	Антуан Жу Сесиль Пьеро		<8600 процессоро-часов ^{[ количественно ]}
	3 ^6 · 163	27 января 2014 г.	Гора Адж Альфред Менезес Томаз Оливейра Франсиско Родригес-Энрикес		1201 процессор-час
	3 ^6 · 97	2012	совместная команда Fujitsu, NICT и Университета Кюсю ^{[ ВОЗ? ]}
	3 ^6 · 71
"умеренный"	п ²	25 июня 2014 г.	Разван Барбулеску Пьеррик Годри Аврора Гилевич Франсуа Морен		68 CPU-дней + 30 GPU-часов	Это поле является расширением поля простых чисел степени 2, где p — простое число из 80 цифр. ^[31]
	33341353 ⁵⁷	6 января 2013 г.
	33553771 ⁴⁷
	370801 ³⁰	9 ноября 2005 г.
	65537 ²⁵	24 октября 2005 г.

Эллиптические кривые

Корпорация Certicom выпустила серию задач по криптографии на основе эллиптических кривых . Уровень I включает поля размером 109 и 131 бит. Уровень II включает размеры 163, 191, 239, 359 бит. В настоящее время все задачи уровня II считаются вычислительно неосуществимыми. ^[32]

Задачи уровня I, которые были решены: ^[33]

ECC2K-108, включающий дискретный логарифм кривой Коблица в поле 2. ¹⁰⁸ элементы. Премия была вручена 4 апреля 2000 года группе из примерно 1300 человек, которую представлял Роберт Харли. Они использовали распараллеленный ро-метод Полларда с ускорением.
ECC2-109, включающий дискретный логарифм кривой по полю 2. ¹⁰⁹ элементы. Премия была вручена 8 апреля 2004 года группе из примерно 2600 человек, которую представлял Крис Монико. Они также использовали версию распараллеленного ро-метода Полларда, занимающую 17 месяцев календарного времени.
ECCp-109, включающий дискретный логарифм кривой по модулю 109-битного простого числа. Премия была вручена 15 апреля 2002 года группе из примерно 10308 человек, которую представлял Крис Монико. Они снова использовали версию распараллеленного ро-метода Полларда, на которую ушло 549 дней календарного времени.

По состоянию на 2019 год ни одна из 131-битных (или более крупных) задач не решена. ^[update].

В июле 2009 года Йоппе В. Бос, Марсело Э. Кайхара, Торстен Кляйнджунг, Арьен К. Ленстра и Питер Л. Монтгомери объявили, что они выполнили вычисление дискретного логарифма на эллиптической кривой (известной как secp112r1). ^[34]) по модулю 112-битного простого числа. Расчеты проводились на кластере из более чем 200 игровых консолей PlayStation 3 в течение примерно 6 месяцев. Они использовали распространенную распараллеленную версию метода Ро Полларда. ^[35]

В апреле 2014 года Эрих Венгер и Пол Вольфгер из Технологического университета Граца решили дискретный логарифм 113-битной кривой Коблица в экстраполированном виде. ^{[примечание 1]} 24 дня при использовании 18-ядерного кластера Virtex-6 FPGA . ^[36] В январе 2015 года те же исследователи решили дискретный логарифм эллиптической кривой, заданной в 113-битном двоичном поле. Среднее время работы составляет около 82 дней при использовании 10-ядерного кластера Kintex-7 FPGA . ^[37]

2 декабря 2016 года Дэниел Дж. Бернштейн , Сюзанна Энгельс , Таня Ланге , Рубен Нидерхаген , Кристоф Паар , Петер Швабе и Ральф Циммерман объявили о решении общей задачи дискретного логарифмирования эллиптической кривой с длиной 117,35 бит на двоичной кривой с использованием оптимизированного алгоритма. Реализация FPGA параллельной версии ро-метода Полларда. Атака продолжалась около шести месяцев на 64–576 FPGA параллельно. ^[38]

23 августа 2017 года Такуя Кусака, Шо Джоичи, Кен Икута, доктор Аль-Амин Хандакер, Ясуюки Ногами, Сатоши Уэхара, Нариёси Ямаи и Сильвен Дюкен объявили, что они решили задачу дискретного логарифмирования на 114-битном «спаривании» дружественная» кривая Баррето – Нерига (BN), ^[39] использование специального свойства секстического скручивания кривой BN для эффективного выполнения случайного блуждания метода ро Полларда. При реализации использовалось 2000 ядер ЦП, и на решение проблемы ушло около 6 месяцев. ^[40]

16 июня 2020 года Александр Зеневич (Zielar) и Жан Люк Понс ( JeanLucPons ) объявили о решении задачи дискретного логарифмирования 114-битной интервальной эллиптической кривой на кривой secp256k1 путем решения 114-битного закрытого ключа в Bitcoin Puzzle Transactions Challenge. Чтобы установить новый рекорд, они использовали собственное программное обеспечение. ^[41] на основе Pollard Kangaroo на 256x графическом процессоре NVIDIA Tesla V100 , и это заняло 13 дней. Двумя неделями ранее — они использовали такое же количество видеокарт для решения 109-битного интервального ECDLP всего за 3 дня.

Записи дискретного логарифма для эллиптических кривых
Имя кривой	Размер поля	Дата объявления	Объявлено	Алгоритм	Время вычисления
ЕСС2К-108	2 ¹⁰⁸	2000	около 1300 человек в лице Роберта Харли	Метод Полларда Ро
ЕСЦп-109	109-битное простое число	2002	около 10308 человек в лице Криса Монико	распараллеленный метод Ро Полларда	549 дней
ЕСС2-109	2 ¹⁰⁹	2004	около 2600 человек в лице Криса Монико	распараллеленный метод Ро Полларда	17 месяцев
secp112r1	112-битное простое число	июль 2009 г.	Йоппе В. Бос Марсело Э. Криминал Торстен Кляйнъунг Арьен К. Ленстра Питер Л. Монтгомери	распространенная распараллеленная версия метода Ро Полларда ^{[ который? ]}	6 месяцев
	2 ¹¹³	апрель 2014 г.	Эрих Венгер Пол Вольфгер		47 дней ^[36]^{[примечание 1]}
	2 ¹¹³	Январь 2015 г.	Эрих Венгер Пол Вольфгер		82 дня ^{[ нужна проверка ]}
	2 ¹²⁷ Интервальный поиск, размер 2 ^117.35	2 декабря 2016 г.	Дэниел Дж. Бернштейн Сюзанна Энгельс Таня Ланге Рубен Нидерхаген Кристоф Паар Питер Швабе Ральф Циммерманн	параллельная версия метода Ро Полларда	6 месяцев от 64 до 576 FPGA
		23 августа 2017 г.	Такуя Кусака Шо Джоичи Кен Икута Мэриленд Аль-Амин Хандакер Yasuyuki Nogami Сатоши Уэхара Нариёси Ямаи Сильвен Дюкен
секп256к1	2 ²⁵⁶ Интервальный поиск, размер 2 ¹¹⁴	16 августа 2020 г.	Александр Зеневич Жан Люк Понс	параллельная версия метода Ро Полларда	13 дней на 256xTesla V100

Примечания

↑ Перейти обратно: Перейти обратно: ^а ^б Вычисления продолжались 47 дней, но не все используемые FPGA были активны все время, а это означало, что это было эквивалентно экстраполированному времени в 24 дня.

Ссылки

↑ Эммануэль Томе, «795-битный факторинг и дискретные логарифмы», 2 декабря 2019 г.
^ Ф. Будо и др., «Сравнение сложности факторизации и дискретного логарифма: эксперимент с 240 цифрами», 10 июня 2020 г.
↑ Торстен Кляйнъюнг, «Дискретные логарифмы в GF( p ) – 768 бит», 16 июня 2016 г.
↑ Антуан Жу, «Дискретные логарифмы в GF( p ) — 130 цифр», 18 июня 2005 г. ^{[ мертвая ссылка ]}
^ Торстен Кляйнъюнг, «Дискретные логарифмы в GF( p ) – 160 цифр», 5 февраля 2007 г.
^ Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джельджели и ЭммануэльТоме, «Дискретные логарифмы в GF( p ) – 180 цифр»
^ Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том, «Килобитное скрытое вычисление дискретного логарифма snfs» , весна IACR, июль 2016 г.
^ Йенс Зумбрегель, «Дискретные логарифмы в GF(2^30750)», 10 июля 2019 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907 .
^ Р. Грейнджер, Т. Кляйнджунг, Дж. Зумбрагель. О задаче дискретного логарифмирования в конечных полях фиксированной характеристики ^{[ постоянная мертвая ссылка ]}. Пер. амер. Математика.Соц. 370, нет. 5 (2018), стр. 3129-3145.
^ Йенс Зумбрегель, «Дискретные логарифмы в GF(2^9234)», 31 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401 .
^ Антуан Жу, «Дискретные логарифмы в GF (2 ⁶¹⁶⁸) [=GF((2 ²⁵⁷) ²⁴)]", 21 мая 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034 .
^ Антуан Жу. Новый алгоритм расчета индексов со сложностью $L(1/4+o(1))$ в очень маленькой характеристике, 2013, http://eprint.iacr.org/2013/095
^ Антуан Жу, «Дискретные логарифмы в GF (2 ⁴⁰⁸⁰)", 22 марта 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682 .
^ Фарук Гологлу и др., О сите функционального поля и влиянии более высоких вероятностей расщепления: применение к дискретным логарифмам в $\mathbb {F} _{2^{1971}}$ , 2013, http://eprint.iacr.org/2013/074 .
^ Антуан Жу, «Дискретные логарифмы в GF (2 ¹⁷⁷⁸)", 11 февраля 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317 .
^ Грейнджер, Роберт, Торстен Кляйнъюнг и Йенс Зумбрегель. «Взлом «128-битной безопасности» суперсингулярных двоичных кривых (или как решать дискретные логарифмы в ${\mathbb {F} }_{2^{4\cdot 1223}}$ и ${\mathbb {F} }_{2^{12\cdot 367}}$ )». arXiv:1402.3668 [cs, Math], 15 февраля 2014 г. https://arxiv.org/abs/1402.3668 .
^ Торстен Кляйнджунг, 17 октября 2014 г., «Дискретные логарифмы в GF (2 ^ 1279)», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410 .
^ Группа CARAMEL: Разван Барбулеску, Сирил Бувье, Жереми Детрей, Пьеррик Годри, Хамза Джелжели, Эммануэль Томе, Марион Видо и Поль Циммерманн, «Дискретный логарифм в GF (2) ⁸⁰⁹) с FFS», 6 апреля 2013 г., http://eprint.iacr.org/2013/197 .
^ Франсиско Родригес-Энрикес, 18 июля 2016 г., «Дискретные логарифмы в GF(3^{6*509})», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8. 1607 .
^ Жу, Антуан; Пьеро, Сесиль. «Улучшение предварительного вычисления полиномиального времени алгоритмов дискретного логарифма представления Фробениуса» (PDF) . Архивировано из оригинала (PDF) 11 декабря 2014 года . Проверено 11 декабря 2014 г.
^ Франсиско Родригес-Энрикес, «Объявление», 27 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401 .
^ Гора Адж, Альфред Менезес, Томаз Оливейра и Франсиско Родригес-Энрикес, «Вычисление дискретных логарифмов в F_{3^{6*137}} и F_{3^{6*163}} с использованием Magma», 26 февраля 2014 г., http //eprint.iacr.org/2014/057 .
^ Университет Кюсю, NICT и лаборатории Fujitsu установили мировой рекорд по криптоанализу криптографии следующего поколения, 2012 г., http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf .
^ Такуя Хаяши и др., Решение 676-битной задачи дискретного логарифма в GF(3 ^{6 н}), 2010, http://eprint.iacr.org/2010/090 .
^ А. Дюран, «Новые рекорды в вычислениях над большими числами», Информационный бюллетень по безопасности, январь 2005 г., http://eric-diehl.com/letter/Newsletter1_Final.pdf. Архивировано 10 июля 2011 г. в Wayback Machine .
^ Антуан Жу, «Дискретные логарифмы в 1425-битном конечном поле», 6 января 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214. .
↑ Перейти обратно: Перейти обратно: ^а ^б Более быстрое вычисление индекса для случая среднего простого числа. Приложение к 1175-битным и 1425-битным конечным полям, Архив Eprint, http://eprint.iacr.org/2012/720
^ Антуан Жу, «Дискретные логарифмы в 1175-битном конечном поле», 24 декабря 2012 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902 . ^{[ мертвая ссылка ]}
^ Мукхопадхьяй, Мадхурима; Саркар, Палаш; Сингх, Шашанк; Томе, Эммануэль (2022). «Новое вычисление дискретного логарифма для среднего простого случая с использованием сита функционального поля» . Достижения в области математики связи . 16 (3): 449. doi : 10.3934/amc.2020119 .
^ Саркар, Палаш; Сингх, Шашанк (2016). «Точная настройка алгоритма сита функционального поля для случая среднего простого числа» . Транзакции IEEE по теории информации . 62 (4): 2233–2253. дои : 10.1109/TIT.2016.2528996 .
↑ Перейти обратно: Перейти обратно: ^а ^б Разван Барбулеску, «Дискретные логарифмы в GF(p^2) --- 160 цифр», 24 июня 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c.1406 .
^ Certicom Corp., «Вызов Certicom ECC», https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html
^ Certicom Research, Certicom ECC Challenge (Certicom Research, 10 ноября 2009 г.), «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 22 октября 2015 года . Проверено 30 декабря 2010 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) .
^ Certicom Research, «SEC 2: Рекомендуемые параметры домена эллиптической кривой» https://www.secg.org/SEC2-Ver-1.0.pdf
^ Джоппе В. Бос и Марсело Э. Кайхара, «Вычисления PlayStation 3 преодолевают барьер 2 ^ 60: решено 112-битное простое ECDLP», Лаборатория криптологических алгоритмов EPFL - LACAL, http://lacal.epfl.ch/112bit_prime
↑ Перейти обратно: Перейти обратно: ^а ^б Эрих Венгер и Пол Вольфгер, «Решение дискретного логарифма 113-битной кривой Коблица с помощью кластера FPGA» http://eprint.iacr.org/2014/368
^ Эрих Венгер и Пол Вольфгер, «Сложнее, лучше, быстрее, сильнее — вычисления дискретного логарифма по эллиптической кривой на FPGA» http://eprint.iacr.org/2015/143/
^ Рубен Нидерхаген, «117,35-битный ECDLP на бинарной кривой», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612
^ «114-битное ECDLP на кривой BN решено» . isec.ec.okayama-u.ac.jp . 23 августа 2017 года. Архивировано из оригинала 27 мая 2018 года . Проверено 3 мая 2018 г.
^ Кусака, Такуя; Джоичи, Шо; Икута, Кен; Хандакер, доктор медицинских наук. Аль-Амин; Ногами, Ясуюки; Уэхара, Сатоши; Ямаи, Нариёси; Дюкен, Сильвен (2018). «Решение 114-битного ECDLP для кривой Баррето – Наэрига» (PDF) . Информационная безопасность и криптология – ICISC 2017 . Конспекты лекций по информатике. Том. 10779. Спрингер. стр. 231–244. дои : 10.1007/978-3-319-78556-1_13 . ISBN 978-3-319-78555-4 .
^ Понс, Жан-Люк; Зеневич, Александр (17 января 2022 г.). «Кенгуру Полларда для SECPK1» . Гитхаб .

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

Вычисления дискретных логарифмов, отсортированные по дате

[extrapolated47to24-36] Перейти обратно: Перейти обратно: ^а ^б Вычисления продолжались 47 дней, но не все используемые FPGA были активны все время, а это означало, что это было эквивалентно экстраполированному времени в 24 дня.

[1] Эммануэль Томе, «795-битный факторинг и дискретные логарифмы», 2 декабря 2019 г.

[2] Ф. Будо и др., «Сравнение сложности факторизации и дискретного логарифма: эксперимент с 240 цифрами», 10 июня 2020 г.

[3] Торстен Кляйнъюнг, «Дискретные логарифмы в GF( p ) – 768 бит», 16 июня 2016 г.

[4] Антуан Жу, «Дискретные логарифмы в GF( p ) — 130 цифр», 18 июня 2005 г. ^{[ мертвая ссылка ]}

[5] Торстен Кляйнъюнг, «Дискретные логарифмы в GF( p ) – 160 цифр», 5 февраля 2007 г.

[6] Сирил Бувье, Пьеррик Годри, Лоран Имбер, Хамза Джельджели и ЭммануэльТоме, «Дискретные логарифмы в GF( p ) – 180 цифр»

[7] Джошуа Фрид, Пьеррик Годри, Надя Хенингер, Эммануэль Том, «Килобитное скрытое вычисление дискретного логарифма snfs» , весна IACR, июль 2016 г.

[8] Йенс Зумбрегель, «Дискретные логарифмы в GF(2^30750)», 10 июля 2019 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907 .

[9] Р. Грейнджер, Т. Кляйнджунг, Дж. Зумбрагель. О задаче дискретного логарифмирования в конечных полях фиксированной характеристики ^{[ постоянная мертвая ссылка ]}. Пер. амер. Математика.Соц. 370, нет. 5 (2018), стр. 3129-3145.

[10] Йенс Зумбрегель, «Дискретные логарифмы в GF(2^9234)», 31 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401 .

[11] Антуан Жу, «Дискретные логарифмы в GF (2 ⁶¹⁶⁸) [=GF((2 ²⁵⁷) ²⁴)]", 21 мая 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034 .

[12] Антуан Жу. Новый алгоритм расчета индексов со сложностью $L(1/4+o(1))$ в очень маленькой характеристике, 2013, http://eprint.iacr.org/2013/095

[13] Антуан Жу, «Дискретные логарифмы в GF (2 ⁴⁰⁸⁰)", 22 марта 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682 .

[14] Фарук Гологлу и др., О сите функционального поля и влиянии более высоких вероятностей расщепления: применение к дискретным логарифмам в $\mathbb {F} _{2^{1971}}$ , 2013, http://eprint.iacr.org/2013/074 .

[15] Антуан Жу, «Дискретные логарифмы в GF (2 ¹⁷⁷⁸)", 11 февраля 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317 .

[16] Грейнджер, Роберт, Торстен Кляйнъюнг и Йенс Зумбрегель. «Взлом «128-битной безопасности» суперсингулярных двоичных кривых (или как решать дискретные логарифмы в ${\mathbb {F} }_{2^{4\cdot 1223}}$ и ${\mathbb {F} }_{2^{12\cdot 367}}$ )». arXiv:1402.3668 [cs, Math], 15 февраля 2014 г. https://arxiv.org/abs/1402.3668 .

[17] Торстен Кляйнджунг, 17 октября 2014 г., «Дискретные логарифмы в GF (2 ^ 1279)», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410 .

[18] Группа CARAMEL: Разван Барбулеску, Сирил Бувье, Жереми Детрей, Пьеррик Годри, Хамза Джелжели, Эммануэль Томе, Марион Видо и Поль Циммерманн, «Дискретный логарифм в GF (2) ⁸⁰⁹) с FFS», 6 апреля 2013 г., http://eprint.iacr.org/2013/197 .

[19] Франсиско Родригес-Энрикес, 18 июля 2016 г., «Дискретные логарифмы в GF(3^{6*509})», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8. 1607 .

[20] Жу, Антуан; Пьеро, Сесиль. «Улучшение предварительного вычисления полиномиального времени алгоритмов дискретного логарифма представления Фробениуса» (PDF) . Архивировано из оригинала (PDF) 11 декабря 2014 года . Проверено 11 декабря 2014 г.

[21] Франсиско Родригес-Энрикес, «Объявление», 27 января 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401 .

[22] Гора Адж, Альфред Менезес, Томаз Оливейра и Франсиско Родригес-Энрикес, «Вычисление дискретных логарифмов в F_{3^{6*137}} и F_{3^{6*163}} с использованием Magma», 26 февраля 2014 г., http //eprint.iacr.org/2014/057 .

[23] Университет Кюсю, NICT и лаборатории Fujitsu установили мировой рекорд по криптоанализу криптографии следующего поколения, 2012 г., http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf .

[24] Такуя Хаяши и др., Решение 676-битной задачи дискретного логарифма в GF(3 ^{6 н}), 2010, http://eprint.iacr.org/2010/090 .

[25] А. Дюран, «Новые рекорды в вычислениях над большими числами», Информационный бюллетень по безопасности, январь 2005 г., http://eric-diehl.com/letter/Newsletter1_Final.pdf. Архивировано 10 июля 2011 г. в Wayback Machine .

[26] Антуан Жу, «Дискретные логарифмы в 1425-битном конечном поле», 6 января 2013 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214. .

[Joux-ePrint-27] Перейти обратно: Перейти обратно: ^а ^б Более быстрое вычисление индекса для случая среднего простого числа. Приложение к 1175-битным и 1425-битным конечным полям, Архив Eprint, http://eprint.iacr.org/2012/720

[28] Антуан Жу, «Дискретные логарифмы в 1175-битном конечном поле», 24 декабря 2012 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902 . ^{[ мертвая ссылка ]}

[29] Мукхопадхьяй, Мадхурима; Саркар, Палаш; Сингх, Шашанк; Томе, Эммануэль (2022). «Новое вычисление дискретного логарифма для среднего простого случая с использованием сита функционального поля» . Достижения в области математики связи . 16 (3): 449. doi : 10.3934/amc.2020119 .

[30] Саркар, Палаш; Сингх, Шашанк (2016). «Точная настройка алгоритма сита функционального поля для случая среднего простого числа» . Транзакции IEEE по теории информации . 62 (4): 2233–2253. дои : 10.1109/TIT.2016.2528996 .

[:0-31] Перейти обратно: Перейти обратно: ^а ^б Разван Барбулеску, «Дискретные логарифмы в GF(p^2) --- 160 цифр», 24 июня 2014 г., https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c.1406 .

[32] Certicom Corp., «Вызов Certicom ECC», https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html

[33] Certicom Research, Certicom ECC Challenge (Certicom Research, 10 ноября 2009 г.), «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 22 октября 2015 года . Проверено 30 декабря 2010 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) .

[34] Certicom Research, «SEC 2: Рекомендуемые параметры домена эллиптической кривой» https://www.secg.org/SEC2-Ver-1.0.pdf

[35] Джоппе В. Бос и Марсело Э. Кайхара, «Вычисления PlayStation 3 преодолевают барьер 2 ^ 60: решено 112-битное простое ECDLP», Лаборатория криптологических алгоритмов EPFL - LACAL, http://lacal.epfl.ch/112bit_prime

[:1-37] Перейти обратно: Перейти обратно: ^а ^б Эрих Венгер и Пол Вольфгер, «Решение дискретного логарифма 113-битной кривой Коблица с помощью кластера FPGA» http://eprint.iacr.org/2014/368

[38] Эрих Венгер и Пол Вольфгер, «Сложнее, лучше, быстрее, сильнее — вычисления дискретного логарифма по эллиптической кривой на FPGA» http://eprint.iacr.org/2015/143/

[39] Рубен Нидерхаген, «117,35-битный ECDLP на бинарной кривой», https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612

[40] «114-битное ECDLP на кривой BN решено» . isec.ec.okayama-u.ac.jp . 23 августа 2017 года. Архивировано из оригинала 27 мая 2018 года . Проверено 3 мая 2018 г.

[41] Кусака, Такуя; Джоичи, Шо; Икута, Кен; Хандакер, доктор медицинских наук. Аль-Амин; Ногами, Ясуюки; Уэхара, Сатоши; Ямаи, Нариёси; Дюкен, Сильвен (2018). «Решение 114-битного ECDLP для кривой Баррето – Наэрига» (PDF) . Информационная безопасность и криптология – ICISC 2017 . Конспекты лекций по информатике. Том. 10779. Спрингер. стр. 231–244. дои : 10.1007/978-3-319-78556-1_13 . ISBN 978-3-319-78555-4 .

[42] Понс, Жан-Люк; Зеневич, Александр (17 января 2022 г.). «Кенгуру Полларда для SECPK1» . Гитхаб .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[примечание 1]

[36]

[37]

[38]

[39]

[40]

[41]