Изучается генерическая сложность проблемы извлечения квадратного корня по простому модулю. Вопрос о вычислительной сложности этой проблемы до сих пор открыт. Однако известны алгоритмы (например, алгоритм Чиполлы), которые являются полиномиальными при условии истинности расширенной гипотезы Римана. Доказывается, что проблема является генерически разрешимой за полиномиальное время. Фактически это означает, что алгоритм Чиполлы работает за полиномиальное время для «почти всех» входов. Понятие «почти все» формализуется введением асимптотической плотности на множестве входных данных.
Скачать электронную версию публикации
Загружен, раз: 3
- Title О генерической сложности проблемы извлечения квадратного корня по простому модулю
- Headline О генерической сложности проблемы извлечения квадратного корня по простому модулю
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 62
- Date:
- DOI 10.17223/20710410/62/9
Ключевые слова
генерическая сложность, квадратный корень по простому модулюАвторы
Ссылки
Erdos Р. Remarks on number theory I // Mat. Lapok. 1961. V. 12. P. 10-17.
Рыбалов A. H. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2(28). С. 54-58.
Adleman L. M. and McCurley K. S. Open problems in number theoretic complexity, II // LNCS. 1994. V.877. P.291-322.
Kapovich L, Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P. 665-694.
Ankeny N. C. The least quadratic non residue // Ann. Math. 1952. V. 55. P. 65-72.
Cipolla М. Un metodo per la risoluzione della congruenza di secondo grado // Rendiconto dell' Accademia delle Scienze Fisiche e Matematiche. Napoli, 1904. V. 10. No. 3. P.144-150, (in Italian).
О генерической сложности проблемы извлечения квадратного корня по простому модулю | Прикладная дискретная математика. 2023. № 62. DOI: 10.17223/20710410/62/9
Скачать полнотекстовую версию
Загружен, раз: 88