The Root Extraction Problem for Generic Braids

María Cumplido Cabello (1, 2) , Juan González-Meneses (3) , Marithania Silvero (4)

1 IMB - Institut de Mathématiques de Bourgogne [Dijon]
2 School of Mathematics - University of Edinburgh
3 DALG-US - Departamento de Algebra [Sevilla]
4 Departamento de Ciencias Integradas [Universidad de Huelva]

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)n3logn) . 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 Δ .

Mots clés: braid groups; algorithms in groups; group-based cryptography; garside groups; conjugacy

Domaines: Mathématiques [math]

María Cumplido Cabello, Juan González-Meneses, Marithania Silvero. The Root Extraction Problem for Generic Braids. Symmetry, 2019, 11 (11), pp.1327. ⟨10.3390/sym11111327⟩. ⟨hal-02428538⟩