  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.
