Trace Expression of $r$-th Root over Finite Field
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$.
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
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd