1993-01-01

# A refinement of h. c. williams?th root algorithm

## Publication

### Publication

*Mathematics of Computation , Volume 61 - Issue 203 p. 475- 483*

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.

Additional Metadata | |
---|---|

Persistent URL | dx.doi.org/10.1090/S0025-5718-1993-1182249-0 |

Journal | Mathematics of Computation |

Citation |
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 |