In the paper [4], the authors generalized the Cipolla-Lehmer method [2][5] for computing square roots in finite fields to the case of r-th roots with r prime, and compared it with the Adleman-Manders-Miller method [1] from the experimental point of view. In this paper, we compare these two methods from the theoretical point of view.

We consider the computation of r-th roots in finite fields. For the computation of square roots (i.e., the case of r=2), there are two typical methods: the Tonelli-Shanks method [7],[10] and the Cipolla-Lehmer method [3],[5]. The former method can be extended to the case of r-th roots with r prime, which is called the Adleman-Manders-Miller method [1]. In this paper, we generalize the Cipolla-Lehmer method to the case of r-th roots in Fq with r prime satisfying r | q-1, and provide an efficient computational procedure of our method. Furthermore, we implement our method and the Adleman-Manders-Miller method, and compare the results.