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.

In this paper, we describe an improvement of integer factorization of k RSA moduli Ni=piqi (1≤i≤k) with implicit hints, namely all pi share their t least significant bits. May et al. reduced this problem to finding a shortest (or a relatively short) vector in the lattice of dimension k obtained from a given system of k RSA moduli, for which they applied Gaussian reduction or the LLL algorithm. In this paper, we improve their method by increasing the determinant of the lattice obtained from the k RSA moduli. We see that, after our improvement, May et al.'s method works smoothly with higher probability. We further verify the efficiency of our method by computer experiments for various parameters.

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.