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

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

Даты:

Принята к публикации:	21 февр. 2022 г.
Поступила в редакцию:	9 дек. 2022 г.
Опубликована в печати:	1 сент. 2023 г.
Опубликована online:	1 сент. 2023 г.

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

Web of science:	WOS:001094893100007
Scopus:	2-s2.0-85179097808
РИНЦ:	54707426
OpenAlex:	W4405723611

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

Альметрики: