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.


How can read full posts