Short question

mart_r · 2009-01-10, 23:32

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?

CRGreathouse · 2009-01-11, 00:44

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

Random Poster · 2009-01-11, 01:04

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

mart_r · 2009-01-11, 16:06

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.

CRGreathouse · 2009-01-11, 17:57

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

mart_r · 2009-01-11, 19:00

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)

CRGreathouse · 2009-01-11, 19:12

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.

philmoore · 2009-01-11, 23:00

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.

2009-01-10, 23:32	#1
mart_r Dec 2008 you know...around... 2·5²·17 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Short Assignments	Unregistered	Information & Answers	5	2009-03-02 17:29
Back from a short hiatus...	mdettweiler	No Prime Left Behind	2	2009-02-20 16:26
Can I cut an ECM assignment short?	Mr. P-1	Information & Answers	7	2009-02-19 15:05
Short term goal	em99010pepe	No Prime Left Behind	94	2008-03-24 21:02
Short-term goal	em99010pepe	Operation Billion Digits	8	2005-11-26 22:53

2009-01-11, 23:00	#8
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 10001100000₂ 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.