## 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)n^{3} 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 language | English |
---|---|

Article number | 1327 |

Journal | Symmetry |

Volume | 11 |

Issue number | 11 |

Early online date | 23 Oct 2019 |

DOIs | |

Publication status | Published - Nov 2019 |

## Keywords

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

## ASJC Scopus subject areas

- Computer Science (miscellaneous)
- Chemistry (miscellaneous)
- General Mathematics
- Physics and Astronomy (miscellaneous)