2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.





Начать новую тему Ответить на тему
 
 Дискретный логарифм (последние новости)
Сообщение01.12.2017, 11:06 


01/12/17
3
День добрый!

Когда-то давно мне приходилось заниматься реализацией кодов. Я помню, что в то время достаточно насущной была проблема логарифмирования и антилогарифмирования в конечном поле. Кто-нибудь в курсе, как сейчас обстоят дела с дискретным логарифмированием в полях порядка $p^n$? Особый интерес, как обычно, к полям характеристики 2. Какие успехи ныне в этом деле?
Удалось найти не совсем свежие источники в которых сказано о проблемах уже при степени $n=512$. Например:
https://www.osp.ru/os/2002/07-08/181696/

Каково приемлемое время вычисления в полях больших порядков в настоящее время? Какие методы наиболее эффективны? Какова их сложность?
И самое главное: изрыл весь интернет, но так и не нашел, кому эта мега задача мега интересна сугубо в практическом плане. Ни одной компании, ни одной организации... Такое ощущение, что ее уже кто-то давно решил...

Спасибо.

 Профиль  
                  
 
 Re: Дискретный логарифм (последние новости)
Сообщение01.12.2017, 12:09 
Заслуженный участник
Аватара пользователя


06/10/08
5929
Evgeniy Vlasov в сообщении #1270634 писал(а):
Когда-то давно мне приходилось заниматься реализацией кодов. Я помню, что в то время достаточно насущной была проблема логарифмирования и антилогарифмирования в конечном поле. Кто-нибудь в курсе, как сейчас обстоят дела с дискретным логарифмированием в полях порядка $p^n$? Особый интерес, как обычно, к полям характеристики 2. Какие успехи ныне в этом деле?
C полями малой характеристики как раз все плохо, в том смысле, что там недавно нашли квазиполиномиальный (и применимый на практике) алгоритм. И ломали поля размера $2^{\sim 9000}$. Вот недавние обзоры:
https://link.springer.com/chapter/10.10 ... -10683-0_2
https://link.springer.com/article/10.10 ... 015-0147-6
http://eprint.iacr.org/2016/914.pdf

Evgeniy Vlasov в сообщении #1270634 писал(а):
И самое главное: изрыл весь интернет, но так и не нашел, кому эта мега задача мега интересна сугубо в практическом плане. Ни одной компании, ни одной организации... Такое ощущение, что ее уже кто-то давно решил...
Я подозреваю, ФСБ и NSA заинтересованы.

 Профиль  
                  
 
 Re: Дискретный логарифм (последние новости)
Сообщение01.12.2017, 12:55 


01/12/17
3
Цитата:
C полями малой характеристики как раз все плохо, в том смысле, что там недавно нашли квазиполиномиальный (и применимый на практике) алгоритм.
А почему плохо-то? :-)

Цитата:
Первые два источника платные. В последнем сказано, что поля больших порядков "ломаются" за какое-то невменяемое время. Кроме того, там несвязанные методы для отдельных частных случаев. Есть какой-то общеприменимый алгоритм, пусть для порядков поменьше, но тем не менее для общего случая? И каковы все же текущие скорости вычислений, скажем, для $100\leqslant n\leqslant1000$?

Цитата:
Я подозреваю, ФСБ и NSA заинтересованы.
Может, поэтому и нет сведений? :-)

 Профиль  
                  
 
 Re: Дискретный логарифм (последние новости)
Сообщение01.12.2017, 16:46 
Аватара пользователя


11/06/12
7768
Минск
Evgeniy Vlasov в сообщении #1270657 писал(а):
Первые два источника платные.


Изображение

Раз, два.

 Профиль  
                  
 
 Re: Дискретный логарифм (последние новости)
Сообщение08.12.2017, 14:10 


01/12/17
3
Aritaborian в сообщении #1270709 писал(а):
Evgeniy Vlasov в сообщении #1270657 писал(а):
Первые два источника платные.

Раз, два.
Всегда знал, что мир не без добрых людей :-)
Вопрос тем не менее открыт...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group