Дискретный логарифм (последние новости)

[Evgeniy Vlasov]

День добрый!

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

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

Спасибо.

[Xaositect]

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 заинтересованы.

[Evgeniy Vlasov]

Цитата:

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

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

Цитата:

Я подозреваю, ФСБ и NSA заинтересованы.

Может, поэтому и нет сведений?

[Aritaborian]

Evgeniy Vlasov в сообщении #1270657 писал(а):

Первые два источника платные.

Раз, два.

[Evgeniy Vlasov]

Aritaborian в сообщении #1270709 писал(а):

Evgeniy Vlasov в сообщении #1270657 писал(а):

Первые два источника платные.

Раз, два.

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