@article{10272/17584,
year = {2019},
month = {11},
url = {http://hdl.handle.net/10272/17584},
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 D), consisting of either a single
orbit conjugated to itself by D or two orbits conjugated to each other by D.},
organization = {Authors partially supported by the Spanish research project MTM2016-76453-C2-1-P and FEDER. First
author was also supported by EPSRC New Investigator Award EP/S010963/1. Third author was also supported by
the Basque Government grant IT974-16 and Centro de Estudios Avanzados en Física, Matemáticas y Computación de
la Universidad de Huelva.},
publisher = {MDPI},
keywords = {Braid groups},
keywords = {Algorithms in groups},
keywords = {Group-based cryptography},
title = {The Root Extraction Problem for Generic Braids},
doi = {10.3390/sym11111327},
author = {Cumplido, María and González Meneses, Juan and Silvero, Marithania},
}