Реферат: Изучается генерическая сложность проблемы вычисления функции Эйлера, имеющей важное значение для современной криптографии. Например, на предположении о её трудноразрешимости основывается криптостойкость знаменитой системы шифрования с открытым ключом RSA. Доказывается, что при условии трудноразрешимости этой проблемы в худшем случае и Р = ВРР для её решения не существует полиномиального сильно генерического алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему. Таким образом, этот результат обосновывает применение проблемы вычисления функции Эйлера в криптографии с открытым ключом. Для доказательства теоремы используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основной идеей этого метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково.

Библиографическая ссылка: Рыбалов А.Н.
О генерической сложности проблемы вычисления функции Эйлера
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. №65. С.110-117. DOI: 10.17223/20710410/65/6 WOS РИНЦ OpenAlex

Даты:

Опубликована в печати:	11 нояб. 2024 г.
Опубликована online:	11 нояб. 2024 г.

Идентификаторы БД:

Web of science:	WOS:001484036100006
РИНЦ:	71496030
OpenAlex:	W4403558831

Цитирование в БД: Пока нет цитирований

Альметрики: