International Association
for Cryptologic Research

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