Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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

Authors: Kenneth S. Williams and Kenneth Hardy
Journal: Math. Comp. 61 (1993), 475-483
MSC: Primary 11A15; Secondary 11A07, 11Y16
MathSciNet review: 1182249
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11A15, 11A07, 11Y16

Retrieve articles in all journals with MSC: 11A15, 11A07, 11Y16

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society