A refinement of h. c. williams?th root algorithm
Let p and q be primes such that p = 1 (mod q). Let a be an integer such that a<P-1>/« s 1 (mod p). In 1972, H. C. Williams gave an algorithm which determines a solution of the congruence xq = a (mod p) in 0(<73logp) steps, once an integer b has been found such that (bq -a)^"1^'1 ^ 0, 1 (mod p). A step is an arithmetic operation (mod p) or an arithmetic operation on 17-bit integers. We present a refinement of this algorithm which determines a solution in 0(qA)+0(q1o%p) steps, once b has been determined. Thus the new algorithm is better when q is small compared with p.
|Journal||Mathematics of Computation|
Williams, K.S, & Hardy, K. (Kenneth). (1993). A refinement of h. c. williams?th root algorithm. Mathematics of Computation, 61(203), 475–483. doi:10.1090/S0025-5718-1993-1182249-0