On the Cipolla-Lehmer type algorithms in finite fields.

In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams in 1972, and later improved by K. S. Williams and K. Hardy in 1993. For a given r-th power residue c∈Fq where r is an odd prime, the algorithm of H. C. Williams determines a solution of Xr=c in O(r3logq) multiplications in Fq, and the algorithm of K. S. Williams and K. Hardy finds a solution in O(r4+r2logq) multiplications in Fq. Our refinement finds a solution in O(r3+r2logq) multiplications in Fq. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SageMath shows a substantial speed-up compared with the existing algorithms. It should be mentioned that our method also works for a composite r. [ABSTRACT FROM AUTHOR]