Изучается генерическая сложность проблемы факторизации целых чисел. Данная проблема, восходящая ещё к Гауссу, имеет важное значение для современной криптографии. Например, на предположении о её трудноразрешимости основывается криптостойкость системы шифрования с открытым ключом RSA. В работе доказывается, что при условиях трудноразрешимости этой проблемы в худшем случае и Р = ВРР для её решения не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к единице. Для доказательства используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основным ингредиентом этого метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково.
Скачать электронную версию публикации
Загружен, раз: 3
- Title О генерической сложности проблемы факторизации целых чисел
- Headline О генерической сложности проблемы факторизации целых чисел
- Publesher
Tomsk State University
- Issue Прикладная дискретная математика 61
- Date:
- DOI 10.17223/20710410/61/7
Ключевые слова
генерическая сложность, факторизация целых чиселАвторы
Ссылки
Adleman L. М. and McCurley К. S. Open problems in number theoretic complexity, II // LNCS. 1994. V.877. P.291-322.
Rivest R., Shamir A., and Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Commun. ACM. 1978. V. 21. Iss.2. P.120-126.
Рыбалов A. H. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2(28). С. 54-58.
Рыбалов А. Н. О генерической сложности проблемы дискретного логарифма // Прикладная дискретная математика. 2016. №3 (33). С. 93-97.
Рыбалов А. Н. О генерической сложности проблемы извлечения корня в группах вычетов // Прикладная дискретная математика. 2017. №38. С. 95-100.
Kapovich L., Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P. 665-694.
Impagliazzo R. and Wigderson A. p = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma. Proc. 29th STOC. El Paso, ACM, 1997. P.220-229.

О генерической сложности проблемы факторизации целых чисел | Прикладная дискретная математика. 2023. № 61. DOI: 10.17223/20710410/61/7
Скачать полнотекстовую версию
Загружен, раз: 202
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Telegram