Trace expression of $r$-th root over finite field
J. Korean Math. Soc. 2020 Vol. 57, No. 4, 1019-1030
https://doi.org/10.4134/JKMS.j190569
Published online July 1, 2020
Gook Hwa Cho, Namhun Koo, Soonhak Kwon
Ewha Womans University; 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
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).
Downloads: Full-text PDF   Full-text HTML

   

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