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=x2+y2, 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.
Enter p (a prime of the form 4n+1):

Last modified 1st September 2002
Return to main page