Paper 2013/024
New Cube Root Algorithm Based on Third Order Linear Recurrence Relation in Finite Field
Gook Hwa Cho, Namhun Koo, Eunhye Ha, and 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 CipollaLehmer 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}+bx1$ with root $\alpha \in \mathbb{F}_{q^{3}}$ such that $Tr(\alpha^{\frac{q^{2}+q2}{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 CipollaLehmer type algorithms.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 cube root algorithmCipollaLehmer algorithm
 Contact author(s)
 shkwon @ skku edu
 History
 20130124: received
 Short URL
 https://ia.cr/2013/024
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/024, author = {Gook Hwa Cho and Namhun Koo and Eunhye Ha and Soonhak Kwon}, title = {New Cube Root Algorithm Based on Third Order Linear Recurrence Relation in Finite Field}, howpublished = {Cryptology ePrint Archive, Paper 2013/024}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/024}}, url = {https://eprint.iacr.org/2013/024} }