J. Korean Math. Soc. Published online March 12, 2020

Gook Hwa Cho, Namhun Koo, and Soonhak Kwon
Ewha Womans University, Sungkyunkwan University

Abstract : Efficient computation of $r$-th root in $\mathbb F_q$ has many
applications in computational number theory and many other related
areas. We present a new $r$-th root formula which generalizes
M\"{u}ller's result on square root, and which provides a possible
improvement of the Cipolla-Lehmer type algorithms for general
case. More precisely, for given $r$-th power $c\in \mathbb F_q$,
we show that there exists $\alpha \in \mathbb F_{q^r}$ such that
$Tr\left(\alpha^\frac{(\sum_{i=0}^{r-1}q^i)-r}{r^2}\right)^r=c$
where $Tr(\alpha)=\alpha+\alpha^q+\alpha^{q^2}+\cdots
+\alpha^{q^{r-1}}$ and $\alpha$ is a root of certain irreducible
polynomial of degree $r$ over $\mathbb F_q$.