- 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

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

Last modified January 21, 1997.