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

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

Dates:

Published print:	Nov 11, 2024
Published online:	Nov 11, 2024

Identifiers:

Web of science:	WOS:001484036100006
Elibrary:	71496030
OpenAlex:	W4403558831

Citing: Пока нет цитирований

Altmetrics: