A refinement of Müller's cube root algorithm (Q1994923)

For a prime number \(p\), finding cube roots in the finite field \(\mathbb{F}_p\) has several applications in computational number theory. For instance, pairing based cryptosystems (see [\textit{D. Boneh} and \textit{M. Franklin}, Lect. Notes Comput. Sci. 2139, 213--229 (2001; Zbl 1002.94023)] and [\textit{I. Duursma} and \textit{H.-S. Lee}, Lect. Notes Comput. Sci. 2894, 111--123 (2003; Zbl 1189.11056)]) using elliptic and hyperelliptic curves requires basic arithmetic operations including cube root computations. Two standard algorithms for cube root extraction in finite fields are available; Adleman-Manders-Miller (AMM) algorithm which is a generalization of the Tonelli-Shanks square root algorithm, and the Cipolla-Lehmer algorithm. The complexity of the AMM algorithm is \(O(\nu_3(p-1)(\log p)^3)\) bit additions, where \(\nu_3(p-1)\) is the largest nonnegative integer \(e\) such that \(3^e\) divides \(p-1\). If \(\nu_3(p-1) \approx \log p\), we get the worst time complexity \(O((\log p)^4)\). However, the complexity of the Cipolla-Lehmer algorithm is \(O((\log p)^3)\), and it does not depend on \((\nu_3(p-1)\). It follows that, compared with the Cipolla-Lehmer algorithm, the AMM algorithm becomes inefficient for primes \(p\) with large \((\nu_3(p-1)\). \textit{H. C. Williams} [in: Proc. 3rd Southeast. Conf. Combinat., Graph Theory, Computing, Florida Atlantic Univ., Boca Raton. 451--462 (1972; Zbl 0265.10001)] gave a \(q^{\mathrm{th}}\) root algorithm, requiring \(22 \log p\) multiplications. A refinement of this algorithm was given in [\textit{K. S. Williams} and \textit{K. Hardy}, Math. Comput. 61, No. 203, 475--483 (1993; Zbl 0782.11040)] by Williams-Hardy. This algorithm requires \(14.5 \log p\) multiplications. \textit{S. Müller} [Fields Inst. Commun. 41, 293--304 (2004; Zbl 1089.11069)] gave a fast algorithm which needs only \(8.5 \log p\) multiplications. In this paper, the authors present an algorith (an improvement of Müller's algorithm) which needs \(7.5 \log p\) multiplications in the field \(\mathbb{F}_p\).