20090110, 23:32  #1 
Dec 2008
you know...around...
677 Posts 
Short question
Now, we all know that if n=4m+1 is prime it can be expressed as the sum of two squares in only one way.
I was wondering if this is also true the other way round, i.e. if n=4m+1 can be written as the sum of two squares in only one way (Edit: and gcd(a;b)=1), does that mean n is prime? And if so, how efficient would that test be? I mean, checking the possibilities of a²+b²=n. Surely not as fast as APRCL or ECPP, but I think it could be more efficient than trial division? Last fiddled with by mart_r on 20090110 at 23:41 
20090111, 00:44  #2  
Aug 2006
1011101011011_{2} Posts 
Quote:
Checking each possibility as the sum of two squares takes O(sqrt (n) * log n). 

20090111, 01:04  #3  
Dec 2008
179_{10} Posts 
Quote:


20090111, 16:06  #4  
Dec 2008
you know...around...
677 Posts 
Aha. Good to know.
Quote:
And surely there are even finer techniques to find sums of squares. But I don't know very much about it. Last fiddled with by mart_r on 20090111 at 16:08 

20090111, 17:57  #5 
Aug 2006
3·1,993 Posts 
If you only need to test 1% of the possibilities, that's O(sqrt n * log n).

20090111, 19:00  #6 
Dec 2008
you know...around...
677 Posts 

20090111, 19:12  #7 
Aug 2006
3×1,993 Posts 
Basically, yes. The dominant term is sqrt(n), just like for trial division. Both have a large number of possible optimizations, so it's not clear which would be practically faster, but neither could be used for large numbers.

20090111, 23:00  #8 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011111_{2} Posts 
Euler, for the record, did use this as a primality proving method. In practice, you can sieve out which nx^2 are not squares modulo 2, 3, 5, 7, etc. very quickly. In the end, you need test very few numbers of this form to see if they are actually perfect squares. I do not have the details at hand, but I recall studying this problem a few years ago and coming to the conclusion that finding all representations of n as a sum of squares x^2+y^2 was of approximate order O(n^1/4), although an extra factor of ln n or so would not surprise me. Obviously, we could use this as either a primality proving method or a factoring method.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Short Assignments  Unregistered  Information & Answers  5  20090302 17:29 
Back from a short hiatus...  mdettweiler  No Prime Left Behind  2  20090220 16:26 
Can I cut an ECM assignment short?  Mr. P1  Information & Answers  7  20090219 15:05 
Short term goal  em99010pepe  No Prime Left Behind  94  20080324 21:02 
Shortterm goal  em99010pepe  Operation Billion Digits  8  20051126 22:53 