20050212, 14:56  #1 
Jan 2005
4_{16} Posts 
Integer as sum of two squares of integers
How to efficently check if given integer (from range 110^12) can be represented as sum of two squares of integers, so if n=a^2+b^2.
I know that: a) Those numbers n whose prime divisors of the form 4*m+3 divide n an even number of times can be written as the sum of two squares. b) Jacobi's Two Square Theorem: The number of representations of a positive integer as the sum of two squares is equal to four times the difference of the numbers of divisors congruent to 1 and 3 modulo 4. But when n is big (for example 10^10 or 10^12) it's hard to find all prime divisors of form 4*m+3 or all divisors congruent to 1 and 3 modulo 4. Can anyone give me a hint how to efficently check if n can or cannot be represent as sum of two squares of integers?? 
20050212, 17:17  #2  
"William"
May 2003
Near Grandkid
2·1,187 Posts 
Quote:


20050212, 18:23  #3 
Jan 2005
4_{10} Posts 
OK  I see... But I would like to do it myself... I mean  if I would like to write my own solution, so how can I check efficently if number n can be represented as sum of two squares of integers?? Can anyone give me a hint??

20050222, 05:06  #4  
∂^{2}ω=0
Sep 2002
República de California
11755_{10} Posts 
Quote:
Code:
int x; double n, y, z; /* floatingpoint fudge factor; assumes sqrt() implementation has RO error <= this value */ const double eps = 1.0e12; ... {init n} ... (loop over x, assume x increases with each loop execution) { z = (1.0*x); z = n  z*z; if(z < 0) break; /* assume FP sqrt inexact, so add small fudge factor before truncating */ y = floor(sqrt(z) + eps); if(z == y*y) printf("n = %d^2 + %d^2\n", x, (int)y); } Have fun, Ernst Last fiddled with by ewmayer on 20050222 at 18:02 

20050222, 19:24  #5 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
There is an algorithm for expressing a prime p = 1 mod 4 as the sum of two squares, which I have used in the past, but need to review before I can post details. I just remember that it starts by finding a quadratic nonresidue. I suspect that Dario Alpern ("alpertron" on this forum) uses the same routine in his Java applet. I'll pm him for details, otherwise, I'll eventually try to get the details posted here myself.

20050222, 19:45  #6 
Aug 2002
Buenos Aires, Argentina
10111011001_{2} Posts 
Yes, I'm using that routine. See this page for details.
This means that for composite numbers, we need to factor it. Notice that we don't need to factor the number if we want to express it a sum of three or four squares. See my Sum of squares applet where you can enter expressions. You can even see the decomposition on squares of RSA2048 with this applet. 
20050224, 07:22  #7 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
Thanks, Dario, for the link to your webpage. You are a teacher as well as a scholar! Your algorithm looks like Fermat's method of descent, which is also the first method I used to solve this problem. I eventually found another algorithm called "Cornacchia's algorithm" which solves the problem with fewer steps. I haven't had a chance to look at my notes until tonight or I would have posted earlier. (Having a 5month old baby certainly seems to limit my free time!) So here is the algorithm:
p is a prime = 1 mod 4 Solve p = x^2 + y^2: First find a quadratic nonresidue b to p. (As Dario has said, the easiest way is to check all prime numbers in sequence until we find b with Jacobi(b,p)=1.) x = b^((p1)/4) mod p sqrtp = floor(sqrt(p)) y = p%x if y=1 then done else do while x>sqrtp {r = x%y x = y y = r} 
20120314, 17:35  #8  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3·419 Posts 
Quote:
By the way, for the extension, what is the modification needing to be done to write out the given prime p = 1, 3 (mod 8) into x²+2y² p = 1 (mod 3) into x²+3y² p = 1, 9 (mod 20) into x²+5y² forms? 

20120315, 02:04  #9 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·23·149 Posts 

20120315, 06:54  #10  
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
4E9_{16} Posts 
Quote:
p = 1 (mod 4) uniquely writable into x²+y² p = 1, 3 (mod 8) uniquely writable into x²+2y² p = 1 (mod 3) uniquely writable into x²+3y² what else? p = 1, 9 (mod 20) uniquely writable into x²+5y² ... the forms! cleanly, clearly http://en.wikipedia.org/wiki/Fermat%...of_two_squares (a²+Nb²)(c²+Nd²) = (ac+bd)²+N(adbc)² = (acbd)²+N(ad+bc)² The algorithm please? I think we need to find out the two squares (mod p), such that x²+ky² = 0 (mod p), and then reduce it very similar to the GCD process, so, thus Last fiddled with by Raman on 20120315 at 07:30 

20120315, 08:49  #11  
Mar 2009
2×19 Posts 
Quote:
Last fiddled with by Gammatester on 20120315 at 08:50 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Regarding Squares  a1call  Miscellaneous Math  42  20170203 01:29 
k*b^n+/c where b is an integer greater than 2 and c is an integer from 1 to b1  jasong  Miscellaneous Math  5  20160424 03:40 
A Sum of Squares Problem  MattcAnderson  Puzzles  7  20140817 07:20 
Representation of integer as sum of squares  kpatsak  Math  4  20071029 17:53 
squares or not squares  m_f_h  Puzzles  45  20070615 17:46 