We describe several algorithms for computing e-th roots of elements in a number field K, where e is an odd prime-power integer. In particular, we generalize Couveignes’ and Thomé’s algorithms originally designed to compute square-roots in the context of the General Number Field Sieve algorithm for integer factorization. Our algorithms cover most cases of e and K and their complexity is better than general root finding algorithms. Our (publicly available) Python implementation compares extremely well in performance to the implementation of these generic algorithms in well-known computer algebra softwares, allowing us to obtain reasonable timings even for large degree number fields and huge exponents e, which correspond to previously intractable cases using these softwares.

International audience