I have two completed documents that are available publicly: my analysis of Shanks's algorithm for square roots mod p, and my doctoral dissertation (which includes the Shanks analysis as one chapter). Part of my AB thesis is also here, converted to Postscript.
We rigorously analyze Shanks's algorithm for computing square roots modulo a prime number. The initialization always requires two exponentiations. Averaged over all primes and possible inputs, the body of the algorithm requires 8/3 additional multiplications. We obtain exact values for the mean and variance of the number of additional multiplications for a fixed prime, and finally show that the distribution is asymptotically normal.
This exact analysis of Shanks's algorithm for computing square roots in the integers mod p was presented at the fifth Canadian Number Theory Association conference in Ottawa, Ontario in August, 1996. It has been accepted to appear in the conference proceedings. The latest version (June 25,1997) is available as a dvi file (60K) or in gzipped PostScript (62K).
First, we rigorously analyze Shanks's algorithm for computing square roots modulo a prime number. The algorithm's initialization always requires two exponentiations. Averaged over all primes and possible inputs, the body of Shanks's algorithm requires 8/3 additional multiplications. We obtain exact values for the mean and variance of the number of additional multiplications for a fixed prime, and finally show that the distribution is asymptotically normal.
Next, we consider extensions of Shanks's algorithm. Others have described the extension to rth roots when r is prime. We observe that a slight generalization often works for composite r.Generalizing in a different direction, Shanks's algorithm works unchanged to compute roots in cyclic groups and even in some non-abelian groups. We characterize the groups in which the algorithm correctly computes square roots.
The number of multiplications done by the initialization of Shanks's algorithm depends on the sum of the digits of an input. This leads us to study sums of digits of numbers in arithmetic progressions. We ask about numbers up to x in a given arithmetic progression: How many have digits that sum to a given number? We obtain a simple generating function recurrence that lets us easily find the generating function when x is a power of the numeric base in which the numbers are written.
This recurrence is easily used to derive previous results due to Newman and Dekking counting the multiples of 3 or 5 with even and odd digit sums.
This is my doctoral dissertation, defended on June 9, 1997. It will eventually be available in the University of Wisconsin-Madison library and through UMI, but will probably take several months to work its way through the system. You can get a copy right now, either as a DVI file (210K) or as a gzipped PostScript file (141K)
This was my Bachelor's thesis at Princeton, completed in April, 1990. So far, I've only converted the body from MS Word (Mac version 4.0) to Postscript. I'll finish the conversion some day, but it's troublesome to convert the pictures (which were created using Canvas 3 for Mac). If you want copies of the Mac-specific files, send me e-mail. Get AB thesis in Postscript (60K).