In article <firstname.lastname@example.org>, email@example.com (Thomas Womack) wrote:
=> How can Maple find so quickly that 3*10^36+1 can be written as => => 1674364408217502600^2 + 443287523504161249^2 ?
I don't know.
But, see the end of the section on Sums of Two Squares in Niven, Zuckerman and Montgomery, An Introduction to the Theory of Numbers, 5th ed. On pages 168--9 there's an algorithm for x^2 + y^2 = p, where p is known to be prime.