О генерической сложности проблемы извлечения квадратного корня по простому модулю Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2023, Volume: 62, Pages: 119-123 Pages count : 5 DOI: 10.17223/20710410/62/9 | ||
| Tags | генерическая сложность, квадратный корень по простому модулю | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 22-11-20019 |
Abstract:
Изучается генерическая сложность проблемы извлечения квадратного корня по простому модулю. Вопрос о вычислительной сложности этой проблемы до сих пор открыт. Однако известны алгоритмы (например, алгоритм Чиполлы), которые являются полиномиальными при условии истинности расширенной гипотезы Римана. Доказывается, что проблема является генерически разрешимой за полиномиальное время. Фактически это означает, что алгоритм Чиполлы работает за полиномиальное время для «почти всех» входов. Понятие «почти все» формализуется введением асимптотической плотности на множестве входных данных.
Cite:
Рыбалов А.Н.
О генерической сложности проблемы извлечения квадратного корня по простому модулю
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. Т.62. С.119-123. DOI: 10.17223/20710410/62/9 WOS Scopus РИНЦ OpenAlex
О генерической сложности проблемы извлечения квадратного корня по простому модулю
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. Т.62. С.119-123. DOI: 10.17223/20710410/62/9 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Nov 3, 2023 |
| Published print: | Dec 25, 2023 |
| Published online: | Dec 25, 2023 |
Identifiers:
| Web of science: | WOS:001424879000009 |
| Scopus: | 2-s2.0-85184492796 |
| Elibrary: | 55082642 |
| OpenAlex: | W4403340870 |
Citing:
Пока нет цитирований