RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2016, номер 3(33), страницы 93–97 (Mi pdm556)

Эта публикация цитируется в 5 статьях

Математические основы информатики и программирования

О генерической сложности проблемы дискретного логарифма

А. Н. Рыбалов

Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия

Аннотация: Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. Изучается генерическая сложность классической проблемы дискретного логарифма в полях GF$(p)$, где $p$ – простое. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема дискретного логарифма трудноразрешима в классическом смысле.

Ключевые слова: генерическая сложность, проблема дискретного логарифма, вероятностный алгоритм.

УДК: 510.52

DOI: 10.17223/20710410/33/8



Реферативные базы данных:


© МИАН, 2024