An Algorithmic Look at Some Seventeenth Century Number Theory -A Talk by Kenneth A. Ribet
An algorithmic look at some seventeenth century number theory
Kenneth A. Ribet University of California, Berkeley
December 8, 2011, 4:35 pm in RH302
Suppose that p is a prime number of the form 4k + 1, i.e., a prime congruent to 1 mod 4. In 1654, Fermat proved that p is a sum of two squares. For example, 13 = 32 +22, 41 = 52 +42, 144169 = 3152 + 2122 , 10000000033 = 559132 + 829082, and so on. The most standard textbook proof of Fermat’s result begins with the existence of a square root of −1 mod p and then uses a counting argument that involves a chosen square root.
When we think algorithmically, we are no longer content with the qualitative statement that −1 is the square of some number mod p: we require an algorithm that produces a square root of −1 in an acceptable amount of time. Armed with the desired square root, we’d then like to to decompose p as a sum of two squares in an efficient manner.
My talk will be principally about an algorithm due to Michele Cipolla (1880–1947) for finding square roots modulo p. The algorithm is probabilistic, meaning that it depends on a sequence of random choices, but it has a very short expected running time. I will describe the algorithm at the chalkboard and then implement it in a few lines on my laptop using the free open-source computer algebra package Sage. If there is time, I will explain with Sage how to parlay a square root of −1 into a decomposition of p as a sum of two squares.