# What are the consequences of a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares?

This question is based on this question, in which it is asked if there is a polynomial time algorithm which finds out if a given number is expressible as the sum of two squares. One of the answers pointed out that this problem is essentially as hard as Integer Factorization.

The wiki article on integer factorization says the following.

Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem, the RSA problem. An algorithm which efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.

This prompted me to ask if there were any similar consequences if a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares is discovered?

ADDENDUM: Note that I am interested only in whether the integer can be represented in such a way, not in how it is represented.

• One consequence that springs to mind is that if one had such an algorithm and was able to find multiple expressions as a sum of two squares, one could then use these expressions to determine a (partial) factorization. Apr 2 '11 at 16:38
• Could you elaborate on that please? Apr 2 '11 at 17:09
• If one has $N = a^2+b^2 = c^2+d^2$ for distinct decompositions as sums of squares, then one can use these decompositions to find a factor of $N$ by taking $\gcd(ac+bd,N)$; the resulting number is a nontrivial factor. Apr 2 '11 at 17:30
• @ARupinski: $3^2+4^2=4^2+3^2=25$ but $3*4+4*3=24$, $gcd(24,25)=1$. Something is wrong?
– user6976
Apr 2 '11 at 18:45
• @Mark: truly distinct decompositions - where order doesn't matter, as well as signs. Apr 2 '11 at 20:41

John Brillhart has a short piece in the December 2009 M.A.A. Monthly, I guess Volume 116, pages 928-931, called A Note on Euler's Factoring Problem, giving full detail on using multiple decompositions as $x^2 + n y^2$ for factoring some odd $N.$
• It appears you are a high school student. I encourage you to experiment with actual factoring, for example by getting a copy of the Brillhart article. It is a little early to be saying what you do not wish to learn about.  The Lehmer machine was a bunch of gears with holes. If all the gear holes lined up, a beam of light could be detected by a photoelectric cell, which would instantly stop the machine. Evidently the radio also activated the electric eye, stopping the machine at random. Apr 3 '11 at 2:22