An Algorithmic Look at Some Seventeenth Century Number Theory -A Talk by Kenneth A. Ribet

Lecture / Panel
For NYU Community

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 qual­itative 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 probabilis­tic, 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.