### Serret's algorithm for expressing a prime p=4n+1 as a sum of two squares

This program finds positive integers x, y such that
p=x^{2}+y^{2}, where p is a prime of the form 4n+1.

The algorithm goes back to Serret 1848 and is from the book *Computational
methods in number theory, part 1*, (pp.4-5) edited by H.W. Lenstra and R. Tijdeman.
*Last modified 1st September 2002*

Return to main page