New cube root algorithm based on the third order linear recurrence relations in finite fields

In this paper, we present a new cube root algorithm in the finite field \(\mathbb {F}_{q}\) with \(q\) a power of prime, which extends the Cipolla–Lehmer type algorithms (Cipolla, Un metodo per la risolutione della congruenza di secondo grado, 1903; Lehmer, Computer technology applied to the theory of numbers, 1969). Our cube root method is inspired by the work of Müller (Des Codes Cryptogr 31:301–312, 2004) on the quadratic case. For a given cubic residue \(c \in \mathbb {F}_{q}\) with \(q \equiv 1 \pmod {9}\), we show that there is an irreducible polynomial \(f(x)\) with root \(\alpha \in \mathbb {F}_{q^{3}}\) such that \(Tr\left( \alpha ^{\frac{q^{2}+q-2}{9}}\right) \) is a cube root of \(c\). Consequently we find an efficient cube root algorithm based on the third order linear recurrence sequences arising from \(f(x)\). The complexity estimation shows that our algorithm is better than the previously proposed Cipolla–Lehmer type algorithms.