Welcome to the resource topic for 2013/024
Title:
New Cube Root Algorithm Based on Third Order Linear Recurrence Relation in Finite Field
Authors: Gook Hwa Cho, Namhun Koo, Eunhye Ha, Soonhak Kwon
Abstract:In this paper, we present a new cube root algorithm in finite field \mathbb{F}_{q} with q a power of prime, which extends the Cipolla-Lehmer type algorithms \cite{Cip,Leh}. Our cube root method is inspired by the work of Müller \cite{Muller} on quadratic case. For given cubic residue c \in \mathbb{F}_{q} with q \equiv 1 \pmod{9}, we show that there is an irreducible polynomial f(x)=x^{3}-ax^{2}+bx-1 with root \alpha \in \mathbb{F}_{q^{3}} such that Tr(\alpha^{\frac{q^{2}+q-2}{9}}) is a cube root of c. Consequently we find an efficient cube root algorithm based on third order linear recurrence sequence arising from f(x). Complexity estimation shows that our algorithm is better than previously proposed Cipolla-Lehmer type algorithms.
ePrint: https://eprint.iacr.org/2013/024
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .