A remark on the computation of cube roots in
Nozomu Nishihara, Ryuichi Harasawa, Yutaka Sueyoshi, Aichi Kudo · 2013
We consider the computation of cube roots in finite fields. For the compu- tation of square roots in finite fields, there are two typical methods; the Tonelli-Shanks method (9, 12) and the Cipolla-Lehmer method (4, 6). The former can be extended easily to the case of r-th roots, which is called the Adleman-Manders-Miller method (1), but it seems to be difficult to extend the latter to more general cases. In this paper, we propose two explicit algorithms for realizing the Cipolla-Lehmer method in the case of cube roots for prime fields Fp with p ≡ 1 (mod 3). We implement these methods and compare the results.