A refinement of H. C. Williams’ $q$th root algorithm

Abstract:

Let p and q be primes such that $p \equiv 1 \pmod q$. Let a be an integer such that ${a^{(p - 1)/q}} \equiv 1 \pmod p$. In 1972, H. C. Williams gave an algorithm which determines a solution of the congruence ${x^q} \equiv a \pmod p$ in $O({q^3}\log p)$ steps, once an integer b has been found such that ${({b^q} - a)^{(p - 1)/q}} \nequiv 0,1 \pmod p$. A step is an arithmetic operation $\pmod p$ or an arithmetic operation on q-bit integers. We present a refinement of this algorithm which determines a solution in $O({q^4}) + O({q^2}\log p)$ steps, once b has been determined. Thus the new algorithm is better when q is small compared with p.