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

Рыбалов, Александр Николаевич

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

Дата публикации: 2017

Дата публикации в реестре: 2020-03-03T18:58:44Z

Аннотация:

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность классической проблемы извлечения корня в группах вычетов Z/(m), где m = pq — произведение двух простых чисел. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема извлечения корня трудноразрешима в классическом смысле.

Ключевые слова:
генерическая сложность, проблема извлечения корня в группах вычетов, вероятностные алгоритмы

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2017. № 38. С. 95-100