Cumplido, MaríaGonzález Meneses, JuanSilvero, Marithania2020-03-092020-03-092019-11Cumplido, M., González Meneses, J., Silvero, M. (2019). The Root Extraction Problem for Generic Braids. Symmetry, 11(11), 1327. DOI: https://doi.org/10.3390/sym111113272073-8994http://hdl.handle.net/10272/17584We 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 D), consisting of either a single orbit conjugated to itself by D or two orbits conjugated to each other by D.engAtribución-NoComercial-SinDerivadas 3.0 Españahttp://creativecommons.org/licenses/by-nc-nd/3.0/es/Braid groupsAlgorithms in groupsGroup-based cryptographyjournal article10.3390/sym11111327open access