A refinement of Müller's cube root algorithm

Abstract Let p be a prime such that p ≡ 1 ( mod 3 ) . Let c be a cubic residue ( mod p ) such that c p − 1 3 ≡ 1 ( mod p ) . In this paper, we present a refinement of Muller's algorithm for computing a cube root of c [11] , which also improves Williams' [14] , [15] Cipolla-Lehmer type algorithms. Under the assumption that a suitable irreducible polynomial of degree 3 is given, Muller gave a cube root algorithm which requires 8.5 log ⁡ p modular multiplications. Our algorithm requires only 7.5 log ⁡ p modular multiplications and is based on the recurrence relations arising from the irreducible polynomial h ( x ) = x 3 + c t 3 x − c t 3 for some integer t.