Journal of the
Korean Mathematical Society JKMS

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$.

Keywords: Finite field, trace, $r$-th root, linear recurrence relation, Tonelli-Shanks algorithm, Adleman-Manders-Miller algorithm, Cipolla-Lehmer algorithm

MSC numbers: 11T06, 11Y16, 68W40

Supported by: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No. 2019R1A6A1A11051177). Gook Hwa Cho was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (No. NRF-
2018R1D1A1B07041716). Namhun Koo was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (No. 2016R1A5A1008055). Soonhak Kwon was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. 2016R1D1A1B03931912, No. 2016R1A5A1008055 and No. 2019R1F1A1058920).