ГлавнаяАрхивО генерической сложности проблемы извлечения корня в группах вычетов

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

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность классической проблемы извлечения корня в группах вычетов Z/(m), где m = pq - произведение двух простых чисел. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема извлечения корня трудноразрешима в классическом смысле.
  • Title О генерической сложности проблемы извлечения корня в группах вычетов
  • Headline О генерической сложности проблемы извлечения корня в группах вычетов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 38
  • Date:
  • DOI 10.17223/20710410/38/7
Ключевые слова
генерическая сложность, проблема извлечения корня в группах вычетов, вероятностный алгоритм, generic complexity, problem of finding roots in groups of residues, probabilistic algorithm
Авторы
Ссылки
Kapovich I., 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.
Kapovich I., Miasnikov A., Schupp P., and Shpilrain V. Average-case complexity for the word and membership problems in group theory // Adv. Math. 2005. V. 190. P. 343-359.
Hamkins J. D. and Miasnikov A. G. The halting problem is decidable on a set of asymptotic probability one // Notre Dame J. Formal Logic. 2006. V. 47. No. 4. P.515-524.
Gilman R., Miasnikov A. G., Myasnikov A. D., and Ushakov A. Report on generic case complexity // Herald of Omsk University. 2007. Special Issue. P. 103-110.
Рыбалов А. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2(28). С. 54-58.
Рыбалов А. О генерической сложности проблемы дискретного логарифма // Прикладная дискретная математика. 2016. №3(33). С. 93-97.
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.
Мао В. Современная криптография: теория и практика. М.: Вильямс, 2005. 768с.
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.
Myasnikov A. and Rybalov A. Generic complexity of undecidable problems // J. Symbolic Logic. 2008. V.73. No.2. P.656-673.
Коблиц Н. Курс теории чисел и криптографии. М.: ТВП, 2001. 254 с.
О генерической сложности проблемы извлечения корня в группах вычетов | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/7
О генерической сложности проблемы извлечения корня в группах вычетов | Прикладная дискретная математика. 2017. № 38. DOI: 10.17223/20710410/38/7