input size. So the computational complexity of this algorithm is exponential. An algorithm with a polynomial complexity has been described by Stan Wagon in 1990, based on work by Serret and Hermite (1848), and Cornacchia (1908). Description Given an odd prime in the form , first find such that . This can be done by finding a Quadratic non-residue modulo , say , and letting . Such an will satisfy the condition since quadratic non-residues satisfy . Once is determined, one can apply the Euclidean algorithm with and . Denote the first two remainders that are less than the square root of as and . Then it will be the case that . Example Take . A possible quadratic non-residue for 97 is 13, since . so we let . The Euclidean algorithm applied to 97 and 22 yields: The first two remainders smaller than the square root of 97 are 9 and 4; and indeed we have , as expected. Proofs Fermat usually did not write down proofs of his claims, and he did not provide a proof of this statement. The first proof was found by Euler after much effort and is based on infinite descent. He announced it in two letters to Goldbach, on May 6, 1747 and on April 12, 1749; he published the detailed proof in two articles (between 1752 and 1755). Lagrange gave a proof in 1775 that was based on his study of quadratic forms. This proof was simplified by Gauss in his Disquisitiones Arithmeticae (art. 182). Dedekind gave at least two proofs based on the arithmetic of the Gaussian integers. There is an elegant proof using Minkowski's theorem about convex sets. Simplifying an earlier short proof due to Heath-Brown (who was inspired by Liouville's idea), Zagier presented a non-constructive one-sentence proof in 1990. And more recently Christopher gave a partition-theoretic proof. Euler's proof by infinite descent Euler succeeded in proving Fermat's theorem on sums of two squares in 1749, when he was forty-two years old. He communicated this in a letter to Goldbach dated 12 April 1749. The proof relies on infinite descent, and is only briefly sketched in the letter. The full proof consists in five steps and is published in two papers. The first four steps are Propositions 1 to 4 of the first paper and do not correspond exactly to the four steps below. The fifth step below is