Computing e -th roots in number fields
Olivier Bernard, Pierre-Alain Fouque, Andrea Lesavourey · Society for Industrial and Applied Mathematics eBooks · 2024
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.