Enumerating ways to decompose an integer into the sum of two squares - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T09:07:17Z http://mathoverflow.net/feeds/question/29644 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares Enumerating ways to decompose an integer into the sum of two squares MathMonkey 2010-06-26T22:05:28Z 2012-07-20T21:37:24Z <p>The well known <a href="http://mathworld.wolfram.com/SumofSquaresFunction.html" rel="nofollow">"Sum of Squares Function"</a> tells you <strong>the number</strong> of ways you can represent an integer as the sum of two squares. See the link for details, but it is based on counting the factors of the number N into powers of 2, powers of primes = 1 mod 4 and powers of primes = 3 mod 4.</p> <p>Given such a factorization, it's easy to find the <strong>number</strong> of ways to decompose N into two squares. But how do you efficiently <strong>enumerate</strong> the decompositions?</p> <p>So for example, given N=2*5*5*13*13=8450 , I'd like to generate the four pairs:</p> <p>13*13+91*91=8450</p> <p>23*23+89*89=8450</p> <p>35*35+85*85=8450</p> <p>47*47+79*79=8450</p> <p>The obvious algorithm (I used for the above example) is to simply take i=1,2,3,...,$\sqrt{N/2}$ and test if (N-i*i) is a square. But that can be expensive for large N. Is there a way to generate the pairs more efficiently? I already have the factorization of N, which may be useful.</p> <p>(You can instead iterate between $i=\sqrt{N/2}$ and $\sqrt{N}$ but that's just a constant savings, it's still $O(\sqrt N)$.</p> http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares/29648#29648 Answer by Gerry Myerson for Enumerating ways to decompose an integer into the sum of two squares Gerry Myerson 2010-06-26T22:41:01Z 2010-06-27T23:50:26Z <p>The factorization of $N$ is useful, since $$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$$ There are good algorithms for expressing a prime as a sum of two squares or, what amounts to the same thing, finding a square root of minus one modulo $p$. See, e.g., <a href="http://www.emis.de/journals/AMEN/2005/030308-1.pdf" rel="nofollow">http://www.emis.de/journals/AMEN/2005/030308-1.pdf</a></p> <p>Edit: Perhaps I should add a word about solving $x^2\equiv-1\pmod p$. If $a$ is a quadratic non-residue (mod $p$) then we can take $x\equiv a^{(p-1)/4}\pmod p$. In practice, you can find a quadratic non-residue pretty quickly by just trying small numbers in turn, or trying (pseudo-)random numbers. </p> http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares/29658#29658 Answer by Will Jagy for Enumerating ways to decompose an integer into the sum of two squares Will Jagy 2010-06-27T01:41:32Z 2010-06-27T07:57:03Z <p>This is the simplest case of the Hardy-Muskat-Williams algorithm. Anyway, here is a link to a 1995 paper by Kenneth S. Williams, <a href="http://www.mathstat.carleton.ca/~williams/papers/pdf/202.pdf" rel="nofollow">http://www.mathstat.carleton.ca/~williams/papers/pdf/202.pdf</a> and to the original HMW paper <a href="http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023762-3/S0025-5718-1990-1023762-3.pdf" rel="nofollow">http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023762-3/S0025-5718-1990-1023762-3.pdf</a> .</p> <p>As I'm not sure you are aware of these details, let me point out that if $$4^k \;| \; \; x^2 + y^2$$ then $2^k \; | \; x$ and $2^k \; | \; y.$ That is, you might as well divide your target by powers of 4 before doing anything difficult. Then after you are finished multiply $x,y$ by the appropriate power of $2.$</p> <p>This is very similar. If there is a prime $$q \equiv 3 \pmod 4$$ and $q | n,$ then keep dividing the target by powers of $q^2$ until it is no longer divisible by $q^2.$ If the remaining number is divisible by $q$ there is actually no representation at all. But if $$q^{2k} \;\parallel \; \; x^2 + y^2$$ then $q^k \; | x$ and $q^k \; | y.$ The notation $q^{2k} \;\parallel \; \; x^2 + y^2$ means $q^{2k} \; | \; \; x^2 + y^2$ but it is not true that $q^{2k +1} \; | \; \; x^2 + y^2$</p> <p>Well, that is enough caution. What you really need to know is expressing primes $$p \equiv 1 \pmod 4$$ and indeed $p^m,$ which is not much more difficult. Once you can do that, combine my notes with all possible ways of applying Gerry's multiplication formula (by changing $\pm$ signs and order),</p> http://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares/102771#102771 Answer by unknown (yahoo) for Enumerating ways to decompose an integer into the sum of two squares unknown (yahoo) 2012-07-20T21:37:24Z 2012-07-20T21:37:24Z <p>I wouldn't mind an elaboration on Gerry's hints. For example, N=5*5*13*13*17*17 is going to have 13 representations. What variants of x +/- yi are we multiplying together to come up with those? In Gerry's example, how come we don't look at (2-i) as a term and end up with 8 representations?</p>