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

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

Add to "Quick Collection"

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

Title: О генерической сложности проблемы извлечения корня в группах вычетов
Title: On generic complexity of the problem of finding roots in groups of residues
Creator: Рыбалов, Александр Николаевич
Date: 2017
DOI: 10.17223/20710410/38/7
Description: Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность классической проблемы извлечения корня в группах вычетов Z/(m), где m = pq — произведение двух простых чисел. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема извлечения корня трудноразрешима в классическом смысле.

Created: 10-01-2018

727 Visitors

626 Hits

107 Downloads

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