An Improvement of the Cipolla-Lehmer Type Algorithms
This work provides an incremental improvement for computational number theorists and cryptographers by optimizing root-finding algorithms in finite fields.
The paper tackles the problem of computing r-th roots in finite fields by refining the Cipolla-Lehmer type algorithm, achieving a solution in O(r^3 + r^2 log q) multiplications, which improves upon prior methods with O(r^3 log q) and O(r^4 + r^2 log q) complexities, and implementation results show substantial speed-up.
Let F_q be a finite field with q elements with prime power q and let r>1 be an integer with $q\equiv 1 \pmod{r}$. In this paper, we present a refinement of the Cipolla-Lehmer type algorithm given by H. C. Williams, and subsequently improved by K. S. Williams and K. Hardy. For a given r-th power residue c in 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 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 F_q. Our refinement finds a solution in $O(r^3+r^2\log q)$ multiplications in F_q. Therefore our new method is better than the previously proposed algorithms independent of the size of r, and the implementation result via SAGE shows a substantial speed-up compared with the existing algorithms.