From: bumby@lagrange.rutgers.edu (Richard Bumby) Newsgroups: sci.math Subject: Re: Shanks's algorithm for square roots mod p (??) Date: 7 May 1998 10:58:01 -0400 "Paul Pollack" writes: >Koblitz mentions, in _A Course in Number Theory and Cryptography_, a way to >take square roots modulo p. Roughly, (to find the square root of a with >(a/p)=1) given a quadratic nonresidue n, and a prime p with p-1=2^alpha*s, >we let r=a^((s+1)/2), and b=n^s. We note that r^2/a is a 2^(a-1)th root of >unity, and then we multiply by a suitable power of b (a primitive >2^alpha-th root of unity) [with the binary digits of this power being >determined by a simple iterative procedure] so that (b^2j)*r^2/a=1. >I understand the algorithm (although there might be a silly mistake in the >above description). What I would like to know is who this algorithm should >be attributed to (my guess is Shanks). Does this appear in Shanks's _Solved >and Unsolved Problems in Number Theory_? Is this the same algorithm that >appears in Shanks's `Five number-theoretical algorithms' from the >_Proceedings of the Second Manatoba Conference on Numerical Mathematics_? >Thanks in advance for your help. I don't have all of my notes handy, but (unlike Shanks) I do have my copy of Dickson's History. As a result, I may make some errors in the recent history, but I can trace the method to Tonelli in 1891 (Dickson, ch. VII, footnote 193, page 215). I have written (see "Sums of four squares", in "Number Theory: New York Seminar 1991--1995", Springer, 1996) that the first modern mention of this is in `Five number-theoretical algorithms. The weak point of this method is that you need a quadratic nonresidue, and there is no proof without a fairly strong Riemann hypothesis that this is as easy to find as it seems to be. -- R. T. Bumby ** Rutgers Math || Amer. Math. Monthly Problems Editor 1992--1996 bumby@math.rutgers.edu || Telephone: [USA] 732-445-0277 (full-time message line) FAX 732-445-5530 ============================================================================== From: Bill Dubuque Newsgroups: sci.math Subject: Re: Shanks's algorithm for square roots mod p (??) Date: 10 May 1998 17:49:14 -0400 Paul Pollack wrote: | | Koblitz mentions, in _A Course in Number Theory and Cryptography_, a way | to take square roots modulo p. Roughly, (to find the square root of a with | (a/p)=1) given a quadratic nonresidue n, and a prime p with p-1=2^alpha*s, | we let r=a^((s+1)/2), and b=n^s. We note that r^2/a is a 2^(a-1)th root of | unity, and then we multiply by a suitable power of b (a primitive | 2^alpha-th root of unity) [with the binary digits of this power being | determined by a simple iterative procedure] so that (b^2j)*r^2/a=1. | | I understand the algorithm (although there might be a silly mistake in the | above description). What I would like to know is who this algorithm should | be attributed to (my guess is Shanks). Does this appear in Shanks's _Solved | and Unsolved Problems in Number Theory_? Is this the same algorithm that | appears in Shanks's `Five number-theoretical algorithms' from the | _Proceedings of the Second Manatoba Conference on Numerical Mathematics_? The essence of this algorithm dates back to Tonelli circa 1890. You should be able to find references in Bach and Shallit's bible: Algorithmic Number Theory, MIT Press, 1996, whose biblio is online, cf. in particular for Tonelli: http://math.uwaterloo.ca/~shallit/bib/chap7.bib An Altavista search also uncovered Scott Lindhurst's analysis of Shanks' algorithm from his thesis, cf. http://www.math.wisc.edu/~lindhurs/papers/papers.html I don't believe Shanks presents the algorithm in his book, but does mention to it in passing in Ch IV (Progress), S.68 p.225, where he refers to the paper you cite. Later he speculated on why Gauss missed this and other results, cf. his interesting paper [1]. (this is mostly from memory, so check to be sure) -Bill Dubuque [1] Shanks, Daniel. On Gauss and composition. I, II. Number theory and applications (Banff, AB, 1988), 163--178, 179--204, NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 265, Kluwer Acad. Publ., Dordrecht, 1989. MR 92e:11150 (Reviewer: Duncan A. Buell) 11Y40 (11E16 11R11)