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.

  • $\begingroup$ 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. $\endgroup$
    – ARupinski
    Apr 2 '11 at 16:38
  • $\begingroup$ Could you elaborate on that please? $\endgroup$ Apr 2 '11 at 17:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – ARupinski
    Apr 2 '11 at 17:30
  • $\begingroup$ @ARupinski: $3^2+4^2=4^2+3^2=25$ but $3*4+4*3=24$, $gcd(24,25)=1$. Something is wrong? $\endgroup$
    – user6976
    Apr 2 '11 at 18:45
  • 3
    $\begingroup$ @Mark: truly distinct decompositions - where order doesn't matter, as well as signs. $\endgroup$ 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.$

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.

  • $\begingroup$ I think the Beiler book was an original Dover publication, not a reprint. $\endgroup$ Apr 2 '11 at 22:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Apr 3 '11 at 1:42
  • $\begingroup$ @will:Why wouldn't the Lehmer machine work with a radio operator around? $\endgroup$ Apr 3 '11 at 1:56
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    Apr 3 '11 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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