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

Cite: Рыбалов А.Н.
О генерической сложности проблемы факторизации целых чисел
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2023. №61. С.121-126. DOI: 10.17223/20710410/61/7 WOS Scopus РИНЦ OpenAlex

Dates:

Accepted:	Feb 21, 2022
Submitted:	Dec 9, 2022
Published print:	Sep 1, 2023
Published online:	Sep 1, 2023

Identifiers:

Web of science:	WOS:001094893100007
Scopus:	2-s2.0-85179097808
Elibrary:	54707426
OpenAlex:	W4405723611

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

Altmetrics: