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

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