## 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. – ARupinski Apr 2 2011 at 16:38
Could you elaborate on that please? – Koundinya Vajjha Apr 2 2011 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. – ARupinski Apr 2 2011 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? – Mark Sapir Apr 2 2011 at 18:45
@Mark: truly distinct decompositions - where order doesn't matter, as well as signs. – Dror Speiser Apr 2 2011 at 20:41
show 1 more comment

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.$

Note that this was a principal method for factoring difficult large integers before the advent of electronic computers. See the Dover reprint, Albert H. Beiler, Recreations in the Theory of Numbers, especially pages 239-247, on the Lehmer factoring machine in the 1930's, which worked well except when an amateur short-wave radio operator nearby was active.

-
I think the Beiler book was an original Dover publication, not a reprint. – Gerry Myerson Apr 2 2011 at 22:31
I just assumed. Inside the Beiler book, it says "is a new work published for the first time in 1964." They gave me a copy for doing best in the 1973-1974 Nassau County interscholastic mathematics league competition, my senior year in high school. I am, you see, very old. – Will Jagy Apr 3 2011 at 1:42
@will:Why wouldn't the Lehmer machine work with a radio operator around? – Koundinya Vajjha Apr 3 2011 at 1:56
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. – Will Jagy Apr 3 2011 at 2:22
Thanks a lot for your advice. :) – Koundinya Vajjha Apr 3 2011 at 4:56