Theoretical Comparison of Root Computations in Finite Fields Theoretical Comparison of Root Computations in Finite Fields

In the paper [4], the authors generalized the Cipolla-Lehmer method [2][5] for computing square roots in finite fields to the case of <i>r</i>-th roots with <i>r</i> 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.