Paper 2013/041
Trace Expression of rth Root over Finite Field
Gook Hwa Cho, Namhun Koo, Eunhye Ha, and Soonhak Kwon
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üller's result on square root, and which provides a possible improvement of the CipollaLehmer 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}^{r1}q^i)r}{r^2}\right)^r=c$ where $Tr(\alpha)=\alpha+\alpha^q+\alpha^{q^2}+\cdots +\alpha^{q^{r1}}$ and $\alpha$ is a root of certain irreducible polynomial of degree $r$ over $\mathbb F_q$.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 finite fieldrth rootlinear recurrence relationTonelliShanks algorithmAdlemanMandersMiller algorithmCipollaLehmer algorithm
 Contact author(s)
 shkwon7 @ gmail com
 History
 20130130: revised
 20130129: received
 See all versions
 Short URL
 https://ia.cr/2013/041
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/041, author = {Gook Hwa Cho and Namhun Koo and Eunhye Ha and Soonhak Kwon}, title = {Trace Expression of rth Root over Finite Field}, howpublished = {Cryptology ePrint Archive, Paper 2013/041}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/041}}, url = {https://eprint.iacr.org/2013/041} }