A polynomial time algorithm for the conjugacy problem in Zn o Z

• Bren Cavallo ^[1] ; Delaram Kahrobaei ^[1]
  1. [1] CUNY Graduate Center, New York
• Localización: Reports@SCM: an electronic journal of the Societat Catalana de Matemàtiques, ISSN-e 2385-4227, Vol. 1, Nº. 1, 2014, págs. 55-60
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen
  • català

    En aquest article introduım un algorisme que, en temps polinomial, resol el problema de la conjugacio (en les seves dues variants, de decisio i de cerca) per a grupsde la forma lliure abelia per infinit cıclic, amb els inputs donats en forma normal. Fem aixo adaptant els resultats de Bogopolski–Martino–Maslakova–Ventura a [1] ide Bogopolski–Martino–Ventura a [2], als grups en questio i, en certs casos, usem un algorisme de Kannan–Lipton [7] per a resoldre el problema de l’`orbita a Zn en temps polinomial.

  • English

    In this paper we introduce a polynomial time algorithm that solves both the conjugacy decision and search problems in free abelian-by-innite cyclic groups where the input is elements in normal form. We do this by adapting the work of Bogopolski, Martino, Maslakova, and Ventura in [1] and Bogopolski, Martino, and Ventura in [2], to free abelian-by-innite cyclic groups, and in certain cases apply a polynomial time algorithm for the orbit problem over Zn by Kannan and Lipton [7].Keywords: Conjugacy problem, semidirect product. MSC (2010): Primary 20F10, Secondary 20E06.

• Referencias bibliográficas
  • O Bogopolski, A Martino, O Maslakova, and E Ventura. The conjugacy problem is solvablein free-by-cyclic groups. Bulletin of the...
  • Oleg Bogopolski, Armando Martino, and Enric Ventura. Orbit decidability and the conjugacyproblem for some extensions of groups.Transactions...
  • Volker Diekert, Alexei Miasnikov, and ArminWeiß. Conjugacy in baumslag’s group, generic case complexity, and division in power circuits....
  • B. Eick. Algorithms for Polycyclic Groups. Habilitationsschrift, Universitat Kassel, 2001.
  • Bettina Eick and Delaram Kahrobaei .Polycyclic groups: A new platform for cryptology? arXiv preprint math/0411077, 2004.
  • Edward Formanek.Conjugate separability in polycyclic groups. Journal of Algebra, 42(1):1–10, 1976.
  • Ravindran Kannan and Richard J Lipton. Polynomial-time algorithm for the orbit problem . Journal of the ACM (JACM), 33(4):808–821,...
  • Charles F Miller III.Decision problems forgroups, survey and reflections. InAlgorithmsand classification in combinatorial group...
  • Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov. Group-based Cryptography. Springer, 2008.
  • Vladimir N Remeslennikov. Conjugacy in polycyclic groups. Algebra and Logic, 8(6):404–411,1969.
  • Andrew W Sale. Short conjugators in solvable groups. arXiv preprint arXiv:1112.2721, 2011.
  • Andrew W Sale. Conjugacy length in group extensions. arXiv preprint arXiv:1211.3144, 2012
  • Svetla Vassileva. Polynomial time conjugacyin wreath products and free solvable groups. Groups, Complexity, Cryptology, 3(1):105–120,2011.