Изучается генерическая сложность проблемы вычисления функции Эйлера, имеющей важное значение для современной криптографии. Например, на предположении о её трудноразрешимости основывается криптостойкость знаменитой системы шифрования с открытым ключом RSA. Доказывается, что при условии трудноразрешимости этой проблемы в худшем случае и Р = ВРР для её решения не существует полиномиального сильно генерического алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему. Таким образом, этот результат обосновывает применение проблемы вычисления функции Эйлера в криптографии с открытым ключом. Для доказательства теоремы используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основной идеей этого метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково.
Скачать электронную версию публикации
Загружен, раз: 8
- Title О генерической сложности проблемы вычисления функции Эйлера
- Headline О генерической сложности проблемы вычисления функции Эйлера
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 65
- Date:
- DOI 10.17223/20710410/65/6
Ключевые слова
генерическая сложность, функция ЭйлераАвторы
Ссылки
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.
Рыбалов A. Н. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2 (28). С. 54-58.
Рыбалов А. Н. О генерической сложности проблемы дискретного логарифма // Прикладная дискретная математика. 2016. УЗ (33). С.93-97.
Рыбалов А. Н. О генерической сложности проблемы извлечения корня в группах вычетов // Прикладная дискретная математика. 2017. У 38. С. 95-100.
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.
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.
Вялый M., Катаев А., Шень А. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо. 1999. 192 с.
Agrawal M., Kayal N., and Saxena N. PRIMES is in P // Ann. Math. 2004. V. 160. No. 2. P. 781-793.
О генерической сложности проблемы вычисления функции Эйлера | Прикладная дискретная математика. 2024. № 65. DOI: 10.17223/20710410/65/6
Скачать полнотекстовую версию
Загружен, раз: 65