mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-01-10, 23:32   #1
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

677 Posts
Default 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
mart_r is offline   Reply With Quote
Old 2009-01-11, 00:44   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111010110112 Posts
Default

Quote:
Originally Posted by mart_r View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2009-01-11, 01:04   #3
Random Poster
 
Random Poster's Avatar
 
Dec 2008

17910 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
Random Poster is offline   Reply With Quote
Old 2009-01-11, 16:06   #4
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

677 Posts
Default

Aha. Good to know.

Quote:
Originally Posted by CRGreathouse View Post
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
mart_r is offline   Reply With Quote
Old 2009-01-11, 17:57   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by mart_r View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2009-01-11, 19:00   #6
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

677 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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)
mart_r is offline   Reply With Quote
Old 2009-01-11, 19:12   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2009-01-11, 23:00   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

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.
philmoore is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.