- Current Issue - Ahead of Print Articles - All Issues - Search - Open Access - Information for Authors - Downloads - Guideline - Regulations ㆍPaper Submission ㆍPaper Reviewing ㆍPublication and Distribution - Code of Ethics - For Authors ㆍOnline Submission ㆍMy Manuscript - For Reviewers - For Editors
 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.j190569Published 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