 REU Researcher: Adam Wolfe, Rutgers University, NJ
Email: ajwolfe@eden.rutgers.edu
Mentor: Richard Bumby, Mathematics, Rutgers.
Email: bumby@math.rutgers.edu

A square root of a number b modulo n is a solution x to the equation x² = b (mod n). The basic problem is that of computing square roots when n is a prime, a problem which goes back to the nineteenth century. For small primes, one can solve the problem by exhaustive search; for example, 2 has two square roots (mod 7), but 5 has none. Although there are several known methods for finding such roots for large primes, the problem of finding a process which is sure, fast, and elementary remains open. Some algorithms that have been tried seem to have a fixed probability of success, though there appears to be no systematic theory to explain this.

Wolfe worked with Prof. Richard Bumby (Rutgers Mathematics) on the problem of finding and efficient (polynomial time in the number of digits) elementary algorithm for finding square roots modulo a prime p; deterministic, if possible. This is a well-known and difficult problem in number theory with extensive applications, so it was not expected that he would solve the problem in its entirety. Rather, he worked on a more specific problem---trying to extend Shanks' method for finding square roots by finding the "level" of a number modulo p. The level of a number a is defined to be the smallest u such that a^{k· 2^u} = 1 (mod p) where p is a prime such that p– 1 = k· 2^m, k odd. Shanks' method for finding square roots of high level numbers involves finding another number at a higher level, which seems to be hard. There is a proof based on the Extended Riemann Hypothesis (ERH) that finding a high level number takes no more that O((log_2 p)^3) operations.

Unfortunately the ERH is merely an unproven conjecture, and no-one has found such an algorithm. His research involved finding a deterministic (as opposed to probabilistic) algorithm for finding a higher level number that will run (in the worst case) in polynomial time in the number of digits. Unfortunately, Wolfe did not make lots of progress on this problem (perhaps we should choose our problems more carefully in future summers), but he did learn a lot of math. He writes: "This research has been a challenging and mind-blowing experience. I am amazed at how little we know about number theory and how square rooting numbers modulo a prime can be difficult. Yet I have gained the most knowledge of number theory through this research. By trying to find an algorithm for getting square roots, I was forced to understand and develop difficult concepts in number theory. Perhaps most, if not all concepts in math are developed this way (as a means to solve some kind of problem). The REU program has inspired me to continue my studies in grad school for math and ideally make a living out of math research." WebMaster: dimacs-www@dimacs.rutgers.edu