A refinement of H. C. Williams' th root algorithm
Authors:
Kenneth S. Williams and Kenneth Hardy
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
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: Let p and q be primes such that . Let a be an integer such that
. In 1972, H. C. Williams gave an algorithm which determines a solution of the congruence
in
steps, once an integer b has been found such that
. A step is an arithmetic operation
or an arithmetic operation on q-bit integers. We present a refinement of this algorithm which determines a solution in
steps, once b has been determined. Thus the new algorithm is better when q is small compared with p.
- [1] 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
- [2]
W. S. Anglin,
, Preprint, McGill University, 1987.
- [3] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, https://doi.org/10.1090/S0025-5718-1970-0276200-X
- [4] 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, https://doi.org/10.1090/S0025-5718-1981-0606517-5
- [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] Helmut Hasse, Über die Teilbarkeit durch 2³ der Klassenzahl imaginärquadratischer Zahlkörper mit genau zwei verschiedenen Diskriminantenprimteilern, J. Reine Angew. Math. 241 (1970), 1–6 (German). MR 258792, https://doi.org/10.1515/crll.1970.241.1
- [7] H. W. Gould, Mathematical Notes: Sums of Logarithms of Binomial Coefficients, Amer. Math. Monthly 71 (1964), no. 1, 55–58. MR 1532480, https://doi.org/10.2307/2311306
- [8] 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
- [9] D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
- [10] Robert T. Moenck, On the efficiency of algorithms for polynomial factoring, Math. Comp. 31 (1977), no. 137, 235–250. MR 422193, https://doi.org/10.1090/S0025-5718-1977-0422193-8
- [11] Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, https://doi.org/10.1137/0209024
- [12] Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
- [13] A. Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen, Gött. Nachr. (1891), 344-346.
- [14] H. C. Williams, Some algorithms for solving 𝑥^{𝑞}≡𝑁 (𝑚𝑜𝑑𝑝), 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
Retrieve articles in Mathematics of Computation with MSC: 11A15, 11A07, 11Y16
Retrieve articles in all journals with MSC: 11A15, 11A07, 11Y16
Additional Information
DOI:
https://doi.org/10.1090/S0025-5718-1993-1182249-0
Article copyright:
© Copyright 1993
American Mathematical Society