Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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

1 Answer

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.

share|improve this answer
I think the Beiler book was an original Dover publication, not a reprint. –  Gerry Myerson Apr 2 '11 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 '11 at 1:42
@will:Why wouldn't the Lehmer machine work with a radio operator around? –  Koundinya Vajjha Apr 3 '11 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 '11 at 2:22
Thanks a lot for your advice. :) –  Koundinya Vajjha Apr 3 '11 at 4:56
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.