Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1993-1182249-0
PII: S 0025-5718(1993)1182249-0
Article copyright: © Copyright 1993 American Mathematical Society