Taking roots over high extensions of finite fields

Abstract:

We present a new algorithm for computing $m$-th roots over the finite field $\mathbb {F}_q$, where $q = p^n$, with $p$ a prime, and $m$ any positive integer. In the particular case $m=2$, the cost of the new algorithm is an expected $O(\mathsf {M}(n)\log (p) + \mathsf {C}(n)\log (n))$ operations in $\mathbb {F}_p$, where $\mathsf {M}(n)$ and $\mathsf {C}(n)$ are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give $\mathsf {M}(n) = O(n\log (n) \log \log (n))$ and $\mathsf {C}(n) = O(n^{1.67})$, so our algorithm is subquadratic in $n$.