## Cryptology ePrint Archive: Report 2009/457

A remark on the computation of cube roots in finite fields

Nozomu Nishihara and Ryuichi Harasawa and Yutaka Sueyoshi and Aichi Kudo

Abstract: We consider the computation of cube roots in finite fields. For the computation of square roots in finite fields, there are two typical methods; the Tonelli-Shanks method and the Cipolla-Lehmer method. The former can be extended easily to the case of $r$-th roots, which is called the Adleman-Manders-Miller method, 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 $\mathbb{F}_{p}$ with $p \equiv 1 \ ({\rm mod} \ {3})$. We implement these methods and compare the results.

Category / Keywords: foundations / cube root, finite field, the Tonelli-Shanks method,