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

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

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



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






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


ПДМ, 2017, номер 38, страницы 95–100 (Mi pdm603)  

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

О генерической сложности проблемы извлечения корня в группах вычетов

А. Н. Рыбаловab

a Омский государственный университет им. Ф. М. Достоевского, г. Омск, Россия
b Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия

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

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

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


DOI: https://doi.org/10.17223/20710410/38/7

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

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

Образец цитирования: А. Н. Рыбалов, “О генерической сложности проблемы извлечения корня в группах вычетов”, ПДМ, 2017, № 38, 95–100

Цитирование в формате AMSBIB
\RBibitem{Ryb17}
\by А.~Н.~Рыбалов
\paper О генерической сложности проблемы извлечения корня в~группах вычетов
\jour ПДМ
\yr 2017
\issue 38
\pages 95--100
\mathnet{http://mi.mathnet.ru/pdm603}
\crossref{https://doi.org/10.17223/20710410/38/7}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm603
  • http://mi.mathnet.ru/rus/pdm/y2017/i4/p95

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:68
    Полный текст:20
    Литература:12
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020