The root extraction problem for generic braids

María Cumplido, Juan González-Meneses, Marithania Silvero

Research output: Contribution to journalArticle

Abstract

We show that, generically, finding the k-th root of a braid is very fast. More precisely, we provide an algorithm which, given a braid x on n strands and canonical length l, and an integer k > 1, computes a k-th root of x, if it exists, or guarantees that such a root does not exist. The generic-case complexity of this algorithm is O(l(l + n)n3 log n). The non-generic cases are treated using a previously known algorithm by Sang-Jin Lee. This algorithm uses the fact that the ultra summit set of a braid is, generically, very small and symmetric (through conjugation by the Garside element Δ), consisting of either a single orbit conjugated to itself by Δ or two orbits conjugated to each other by Δ.

Original languageEnglish
Article number1327
JournalSymmetry
Volume11
Issue number11
Early online date23 Oct 2019
DOIs
Publication statusPublished - Nov 2019

Keywords

  • Algorithms in groups
  • Braid groups
  • Group-based cryptography

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Chemistry (miscellaneous)
  • Mathematics(all)
  • Physics and Astronomy (miscellaneous)

Fingerprint Dive into the research topics of 'The root extraction problem for generic braids'. Together they form a unique fingerprint.

  • Cite this

    Cumplido, M., González-Meneses, J., & Silvero, M. (2019). The root extraction problem for generic braids. Symmetry, 11(11), [1327]. https://doi.org/10.3390/sym11111327