 mersenneforum.org > Math Short question
 Register FAQ Search Today's Posts Mark Forums Read 2009-01-10, 23:32 #1 mart_r   Dec 2008 you know...around... 76110 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 APR-CL or ECPP, but I think it could be more efficient than trial division? Last fiddled with by mart_r on 2009-01-10 at 23:41   2009-01-11, 00:44   #2
CRGreathouse

Aug 2006

135338 Posts Quote:
 Originally Posted by mart_r And if so, how efficient would that test be? I mean, checking the possibilities of a²+b²=n. Surely not as fast as APR-CL or ECPP, but I think it could be more efficient than trial division?
I believe checking if a number n is a square can be done in O(log n), with substantial speedups in practice with quadratic reciprocity tests to weed out nonsquares.

Checking each possibility as the sum of two squares takes O(sqrt (n) * log n).   2009-01-11, 01:04   #3
Random Poster

Dec 2008

2638 Posts Quote:
 Originally Posted by mart_r 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?
Yes. Suppose to the contrary that n is the product of and ; then n can be written both as and as .   2009-01-11, 16:06   #4
mart_r

Dec 2008
you know...around...

10111110012 Posts Aha. Good to know.

Quote:
 Originally Posted by CRGreathouse Checking each possibility as the sum of two squares takes O(sqrt (n) * log n).
But I don't have to check every possibility. E.g. it's easy to sort out the cases where n-a² ends in 2, 3, 7, or 8, so only 60% of the a's < sqrt(n) have to be tested, only considering the decimal expansion. And even less candidates remain in higher bases.
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 2009-01-11 at 16:08   2009-01-11, 17:57   #5
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 Originally Posted by mart_r But I don't have to check every possibility. E.g. it's easy to sort out the cases where n-a² ends in 2, 3, 7, or 8, so only 60% of the a's < sqrt(n) have to be tested, only considering the decimal expansion. And even less candidates remain in higher bases.
If you only need to test 1% of the possibilities, that's O(sqrt n * log n).   2009-01-11, 19:00   #6
mart_r

Dec 2008
you know...around...

2F916 Posts Quote:
 Originally Posted by CRGreathouse If you only need to test 1% of the possibilities, that's O(sqrt n * log n).
Couldn't disagree with that.

So I take it it's basically as efficient as trial division. (At least for large n)   2009-01-11, 19:12   #7
CRGreathouse

Aug 2006

3×1,993 Posts Quote:
 Originally Posted by mart_r Couldn't disagree with that. So I take it it's basically as efficient as trial division. (At least for large n)
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.   2009-01-11, 23:00 #8 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts Euler, for the record, did use this as a primality proving method. In practice, you can sieve out which n-x^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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Unregistered Information & Answers 5 2009-03-02 17:29 mdettweiler No Prime Left Behind 2 2009-02-20 16:26 Mr. P-1 Information & Answers 7 2009-02-19 15:05 em99010pepe No Prime Left Behind 94 2008-03-24 21:02 em99010pepe Operation Billion Digits 8 2005-11-26 22:53

All times are UTC. The time now is 06:14.

Wed Jun 29 06:14:51 UTC 2022 up 76 days, 4:16, 1 user, load averages: 0.69, 0.95, 1.02