Paper 2013/041 Original: eprint.iacr.org/2013/041 ↗
Trace Expression of r-th Root over Finite Field
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 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$.
Metadata
- Available format(s)
PDF- Category
- Applications
- Publication info
- Preprint.
- History
- 2013-01-30: last updated
- 2013-01-29: published
- Short URL
- https://ia.cr/2013/041
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2013/041,
author = {Gook Hwa Cho and Namhun Koo and Eunhye Ha and Soonhak Kwon},
title = {Trace Expression of r-th Root over Finite Field},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/041},
year = {2013},
url = {https://eprint.iacr.org/2013/041}
}