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

О генерической сложности проблемы дискретного логарифма | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/8

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. Изучается генерическая сложность классической проблемы дискретного логарифма в полях GF(p), где p - простое. Доказывается, что её естественная подпробле-ма генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема дискретного логарифма трудноразрешима в классическом смысле.
  • Title О генерической сложности проблемы дискретного логарифма
  • Headline О генерической сложности проблемы дискретного логарифма
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(33)
  • Date:
  • DOI 10.17223/20710410/33/8
Ключевые слова
генерическая сложность, проблема дискретного логарифма, вероятностный алгоритм, generic complexity, discrete logarithm problem, 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.
GilmanR., Miasnikov A. G., Myasnikov A. D., and Ushakov A. Report on generic case complexity // Herald of Omsk University. 2007. Special Issue. P. 103-110.
Мао В. Современная криптография: теория и практика. М.: Вильямс, 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.
Rybalov A. Generic complexity of presburger arithmetic // Theory Comput. Systems. 2010. V. 46. No. 1. P. 2-8.
О генерической сложности проблемы дискретного логарифма | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/8
О генерической сложности проблемы дискретного логарифма | Прикладная дискретная математика. 2016. № 3(33). DOI: 10.17223/20710410/33/8