1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Apr 2, 2011 at 16:38
  • $\begingroup$ Could you elaborate on that please? $\endgroup$
    – Koundinya Vajjha
    Commented Apr 2, 2011 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
    Commented Apr 2, 2011 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
    Commented Apr 2, 2011 at 18:45
  • 3
    $\begingroup$ @Mark: truly distinct decompositions - where order doesn't matter, as well as signs. $\endgroup$
    – Dror Speiser
    Commented Apr 2, 2011 at 20:41

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think the Beiler book was an original Dover publication, not a reprint. $\endgroup$
    – Gerry Myerson
    Commented Apr 2, 2011 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
    Commented Apr 3, 2011 at 1:42
  • $\begingroup$ @will:Why wouldn't the Lehmer machine work with a radio operator around? $\endgroup$
    – Koundinya Vajjha
    Commented Apr 3, 2011 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
    Commented Apr 3, 2011 at 2:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .