О генерической сложности проблемы извлечения квадратного корня по простому модулю | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Вых. Данные

Год: 2023, Том: 62, Страницы: 119-123 Страниц : 5 DOI: 10.17223/20710410/62/9

Ключевые слова

генерическая сложность, квадратный корень по простому модулю

Авторы

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

Организации

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

Информация о финансировании (1)

Российский научный фонд

22-11-20019

Изучается генерическая сложность проблемы извлечения квадратного корня по простому модулю. Вопрос о вычислительной сложности этой проблемы до сих пор открыт. Однако известны алгоритмы (например, алгоритм Чиполлы), которые являются полиномиальными при условии истинности расширенной гипотезы Римана. Доказывается, что проблема является генерически разрешимой за полиномиальное время. Фактически это означает, что алгоритм Чиполлы работает за полиномиальное время для «почти всех» входов. Понятие «почти все» формализуется введением асимптотической плотности на множестве входных данных.

Рыбалов А.Н.
О генерической сложности проблемы извлечения квадратного корня по простому модулю
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. Т.62. С.119-123. DOI: 10.17223/20710410/62/9 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	3 нояб. 2023 г.
Опубликована в печати:	25 дек. 2023 г.
Опубликована online:	25 дек. 2023 г.

Web of science:	WOS:001424879000009
Scopus:	2-s2.0-85184492796
РИНЦ:	55082642
OpenAlex:	W4403340870

Пока нет цитирований