IACR News item: 24 January 2013
Gook Hwa Cho, Namhun Koo, Eunhye Ha, Soonhak Kwon
ePrint Reportfield $\\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\\\"{u}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.
Additional news items may be found on the IACR news page.