|
Математические методы криптографии
О генерической сложности проблемы распознавания квадратичных вычетов
А. Н. Рыбаловab a Кафедра математической логики и логического программирования Омского государственного университета им. Ф. М. Достоевского, г. Омск
b Институт математики им. С.Л. Соболева СО РАН, г. Новосибирск
Аннотация:
Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы распознавания квадратичных вычетов в группах вычетов. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема распознавания квадратичных вычетов трудноразрешима в классическом смысле.
Ключевые слова:
генерическая сложность, квадратичный вычет, вероятностный алгоритм.
Образец цитирования:
А. Н. Рыбалов, “О генерической сложности проблемы распознавания квадратичных вычетов”, ПДМ. Приложение, 2015, № 8, 71–73
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma241 https://www.mathnet.ru/rus/pdma/y2015/i8/p71
|
Статистика просмотров: |
Страница аннотации: | 134 | PDF полного текста: | 43 | Список литературы: | 24 |
|