Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


A refinement of H. C. Williams’ $q$th root algorithm
HTML articles powered by AMS MathViewer

by Kenneth S. Williams and Kenneth Hardy PDF
Math. Comp. 61 (1993), 475-483 Request permission


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.
Similar Articles
Additional Information
  • © Copyright 1993 American Mathematical Society
  • Journal: Math. Comp. 61 (1993), 475-483
  • MSC: Primary 11A15; Secondary 11A07, 11Y16
  • DOI:
  • MathSciNet review: 1182249