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

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?)

  • [1] L. Adleman, K. Manders, and G. Miller, On taking roots in finite fields, Proc. 18th Ann. Sympos. Found. Comp. Sci. (Providence, RI, 1977), IEEE Comput. Sci., Long Beach, CA, 1977, pp. 175-178. MR 0502224 (58:19339)
  • [2] W. S. Anglin, $ {x^2} \equiv R \pmod p$, Preprint, McGill University, 1987.
  • [3] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735. MR 0276200 (43:1948)
  • [4] D. G. Cantor and H. J. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587-592. MR 606517 (82e:12020)
  • [5] M. Cipolla, Un metodo per la risoluzione della congruenza di secondo grado, Rend. Accad. Sci. Fis. Mat. Napoli (3) 9 (1903), 154-163.
  • [6] H. Davenport and H. Hasse, Die Nullstellen der Kongruenzzetafunktionen in gewissen zyklischen Fällen, J. Reine Angew. Math. 172 (1934), 151-182. MR 0258792 (41:3438)
  • [7] H. W. Gould, Sums of logarithms of binomial coefficients, Amer. Math. Monthly 71 (1964), 55-58. MR 1532480
  • [8] D. E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, Addison-Wesley, Reading, MA, 1969. MR 0286318 (44:3531)
  • [9] D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory (W. J. LeVeque, ed.), MAA Studies in Math., vol. 6, Math. Assoc. Amer., Washington, DC, 1969, pp. 117-151. MR 0246815 (40:84)
  • [10] R. T. Moenck, On the efficiency of algorithms for polynomial factoring, Math. Comp. 31 (1977), 235-250. MR 0422193 (54:10185)
  • [11] M. O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), 273-280. MR 568814 (81g:12002)
  • [12] D. Shanks, Five number-theoretic algorithms, Proc. Second Manitoba Conf. on Numerical Mathematics, University of Manitoba, Winnipeg, Canada, 1972, pp. 51-70. MR 0371855 (51:8072)
  • [13] A. Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Gött. Nachr. (1891), 344-346.
  • [14] H. C. Williams, Some algorithms for solving $ {x^q} \equiv N \pmod p$, Proc. 3rd Southeastern Conf. on Combinatorics, Graph Theory, and Computing (Florida Atlantic University, 1972), 451-462. MR 0364065 (51:320)

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

American Mathematical Society