2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

Спасибо.

 
 
 
 Re: Дискретный логарифм (последние новости)
Сообщение01.12.2017, 12:09 
Аватара пользователя
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 
Цитата:
C полями малой характеристики как раз все плохо, в том смысле, что там недавно нашли квазиполиномиальный (и применимый на практике) алгоритм.
А почему плохо-то? :-)

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

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

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


Изображение

Раз, два.

 
 
 
 Re: Дискретный логарифм (последние новости)
Сообщение08.12.2017, 14:10 
Aritaborian в сообщении #1270709 писал(а):
Evgeniy Vlasov в сообщении #1270657 писал(а):
Первые два источника платные.

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group