Wagon's algorithm in three easy steps

With interesting stops along the way

If p is an odd prime, Fermat’s theorem says that p can be written as the sum of two squares, but it doesn’t tell you how to find the squares.

Gauss gave a formula for a solution, but the solution is impractical to implement in a computer if p is large.

Wagon’s algorithm scales well. In a series of three posts we work up to a full implementation of the algorithm.

First, we show how to find a number with no square root mod p.

Next, we use this number to find a square root of −1 mod p.

Finally, we use the Euclidean with early stopping to finish Wagon’s algorithm.

Hope you’ve having a happy Valentine’s Day and enjoy the rest of your weekend.