О генерической сложности проблемы факторизации целых чисел | Прикладная дискретная математика. 2023. № 61. DOI: 10.17223/20710410/61/7

Изучается генерическая сложность проблемы факторизации целых чисел. Данная проблема, восходящая ещё к Гауссу, имеет важное значение для современной криптографии. Например, на предположении о её трудноразрешимости основывается криптостойкость системы шифрования с открытым ключом RSA. В работе доказывается, что при условиях трудноразрешимости этой проблемы в худшем случае и Р = ВРР для её решения не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к единице. Для доказательства используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основным ингредиентом этого метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково.
  • Title О генерической сложности проблемы факторизации целых чисел
  • Headline О генерической сложности проблемы факторизации целых чисел
  • Publesher Tomask State UniversityTomsk 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
О генерической сложности проблемы факторизации целых чисел | Прикладная дискретная математика. 2023. № 61. DOI: 10.17223/20710410/61/7