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\in \mathbb {F}_q\) where r is an odd prime, the algorithm of H. C. Williams determines a solution of \(X^r=c\) in \(O(r^3\log q)\) multiplications in \(\mathbb {F}_q\), and the algorithm of K. S. Williams and K. Hardy finds a solution in \(O(r^4+r^2\log q)\) multiplications in \(\mathbb {F}_q\). Our refinement finds a solution in \(O(r^3+r^2\log q)\) multiplications in \(\mathbb {F}_q\). 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.