Аннотация:
Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность классической проблемы извлечения корня в группах вычетов Z/(m), где m=pq – произведение двух простых чисел. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема извлечения корня трудноразрешима в классическом смысле.
Ключевые слова:
генерическая сложность, проблема извлечения корня в группах вычетов, вероятностный алгоритм.
\RBibitem{Ryb17}
\by А.~Н.~Рыбалов
\paper О генерической сложности проблемы извлечения корня в~группах вычетов
\jour ПДМ
\yr 2017
\issue 38
\pages 95--100
\mathnet{http://mi.mathnet.ru/pdm603}
\crossref{https://doi.org/10.17223/20710410/38/7}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm603
https://www.mathnet.ru/rus/pdm/y2017/i4/p95
Эта публикация цитируется в следующих 4 статьяx:
А. Н. Рыбалов, “О генерической сложности проблемы вычисления функции Эйлера”, ПДМ, 2024, № 65, 110–117
А. Н. Рыбалов, “О генерической сложности проблемы дискретного логарифма в последовательностях Люка”, ПДМ, 2024, № 66, 116–122
А. Н. Рыбалов, “О генерической сложности проблемы факторизации целых чисел”, ПДМ, 2023, № 61, 121–126
Rybalov A., Xii International Scientific and Technical Conference Applied Mechanics and Systems Dynamics, Journal of Physics Conference Series, 1210, IOP Publishing Ltd, 2019
Цитирование в формате AMSBIB
Обратная связь: