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

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

- Leonard Adleman, Kenneth Manders, and Gary Miller,
*On taking roots in finite fields*, 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977) IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 175–178. MR**0502224**
W. S. Anglin, ${x^2} \equiv R \pmod p$, Preprint, McGill University, 1987.
- E. R. Berlekamp,
*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**276200**, DOI 10.1090/S0025-5718-1970-0276200-X - David G. Cantor and Hans Zassenhaus,
*A new algorithm for factoring polynomials over finite fields*, Math. Comp.**36**(1981), no. 154, 587–592. MR**606517**, DOI 10.1090/S0025-5718-1981-0606517-5
M. Cipolla, - Helmut Hasse,
*Über die Teilbarkeit durch $2^{3}$ der Klassenzahl imaginärquadratischer Zahlkörper mit genau zwei verschiedenen Diskriminantenprimteilern*, J. Reine Angew. Math.**241**(1970), 1–6 (German). MR**258792**, DOI 10.1515/crll.1970.241.1 - H. W. Gould,
*Mathematical Notes: Sums of Logarithms of Binomial Coefficients*, Amer. Math. Monthly**71**(1964), no. 1, 55–58. MR**1532480**, DOI 10.2307/2311306 - Donald E. Knuth,
*The art of computer programming. Vol. 2: Seminumerical algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR**0286318** - D. H. Lehmer,
*Computer technology applied to the theory of numbers*, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR**0246815** - Robert T. Moenck,
*On the efficiency of algorithms for polynomial factoring*, Math. Comp.**31**(1977), no. 137, 235–250. MR**422193**, DOI 10.1090/S0025-5718-1977-0422193-8 - Michael O. Rabin,
*Probabilistic algorithms in finite fields*, SIAM J. Comput.**9**(1980), no. 2, 273–280. MR**568814**, DOI 10.1137/0209024 - Daniel Shanks,
*Five number-theoretic algorithms*, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR**0371855**
A. Tonelli, - H. C. Williams,
*Some algorithms for solving $x^{q}\equiv N$ $(\textrm {mod}\ p)$*, Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972), Florida Atlantic Univ., Boca Raton, Fla., 1972, pp. 451–462. MR**0364065**

*Un metodo per la risoluzione della congruenza di secondo grado*, Rend. Accad. Sci. Fis. Mat. Napoli (3)

**9**(1903), 154-163.

*Bemerkung über die Auflösung quadratischer Congruenzen*, Gött. Nachr. (1891), 344-346.

## Additional Information

- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp.
**61**(1993), 475-483 - MSC: Primary 11A15; Secondary 11A07, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-1993-1182249-0
- MathSciNet review: 1182249