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

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической сложности проблемы извлечения квадратного корня по простому модулю	642 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/62/9

Title: О генерической сложности проблемы извлечения квадратного корня по простому модулю
Title: On the generic complexity of the square root modulo prime problem
Creator: Рыбалов, Александр Николаевич
Date: 2023
DOI: 10.17223/20710410/62/9
Description: Изучается генерическая сложность проблемы извлечения квадратного корня по простому модулю. Вопрос о вычислительной сложности этой проблемы до сих пор открыт. Однако известны алгоритмы (например, алгоритм Чиполлы), которые являются полиномиальными при условии истинности расширенной гипотезы Римана. Доказывается, что проблема является генерически разрешимой за полиномиальное время. Фактически это означает, что алгоритм Чиполлы работает за полиномиальное время для «почти всех» входов. Понятие «почти все» формализуется введением асимптотической плотности на множестве входных данных.

Created: 15-12-2023

174 Visitors

124 Hits

61 Downloads

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