most recent 30 from http://mathoverflow.net 2013-05-24T10:57:00Z http://mathoverflow.net/feeds/question/60367 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60367/what-are-the-consequences-of-a-polynomial-time-algorithm-for-finding-out-if-a-giv Koundinya Vajjha 2011-04-02T16:03:45Z 2011-04-03T02:03:44Z

<p>This question is based on <a href="http://mathoverflow.net/questions/57981/testing-whether-an-integer-is-the-sum-of-two-squares" rel="nofollow">this question</a>, 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 <a href="http://en.wikipedia.org/wiki/Integer_factorization" rel="nofollow">Integer Factorization</a>. </p> <p>The wiki article on integer factorization says the following.</p> <blockquote> <p>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.</p> </blockquote> <p>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?</p> <p>ADDENDUM: Note that I am interested only in whether the integer can be represented in such a way, not in how it is represented.</p>

http://mathoverflow.net/questions/60367/what-are-the-consequences-of-a-polynomial-time-algorithm-for-finding-out-if-a-giv/60385#60385 Will Jagy 2011-04-02T20:37:31Z 2011-04-02T20:37:31Z

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