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... 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 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

10111010110112 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

17910 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 $a^2+b^2$ and $c^2+d^2$; then n can be written both as $(ac+bd)^2+(ad-bc)^2$ and as $(ad+bc)^2+(ac-bd)^2$.

2009-01-11, 16:06   #4
mart_r

Dec 2008
you know...around...

677 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...

677 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. 100010111112 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.

 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 21:42.

Sun Oct 17 21:42:45 UTC 2021 up 86 days, 16:11, 0 users, load averages: 2.79, 2.67, 2.24