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

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