Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

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

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

А. Н. Рыбалов

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

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

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

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 15-41-04312
Работа поддержана грантом РФФИ № 15-41-04312.


DOI: https://doi.org/10.17223/20710410/33/8

Полный текст: PDF файл (562 kB)
Список литературы: PDF файл   HTML файл

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

Тип публикации: Статья
УДК: 510.52

Образец цитирования: А. Н. Рыбалов, “О генерической сложности проблемы дискретного логарифма”, ПДМ, 2016, № 3(33), 93–97

Цитирование в формате AMSBIB
\RBibitem{Ryb16}
\by А.~Н.~Рыбалов
\paper О генерической сложности проблемы дискретного~логарифма
\jour ПДМ
\yr 2016
\issue 3(33)
\pages 93--97
\mathnet{http://mi.mathnet.ru/pdm556}
\crossref{https://doi.org/10.17223/20710410/33/8}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm556
  • http://mi.mathnet.ru/rus/pdm/y2016/i3/p93

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. Н. Рыбалов, “О генерической сложности проблемы извлечения корня в группах вычетов”, ПДМ, 2017, № 38, 95–100  mathnet  crossref
    2. А. Н. Рыбалов, “О генерической амплификации рекурсивно перечислимых множеств”, Алгебра и логика, 57:4 (2018), 448–455  mathnet  crossref; A. N. Rybalov, “Generic amplification of recursively enumerable sets”, Algebra and Logic, 57:4 (2018), 289–294  crossref  isi
    3. A. Rybalov, “On a generic turing reducibility of computably enumerable sets”, Xii International Scientific and Technical Conference Applied Mechanics and Systems Dynamics, Journal of Physics Conference Series, 1210, IOP Publishing Ltd, 2019, 012122  crossref  isi  scopus
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:109
    Полный текст:51
    Литература:15
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021