We know that for primes , there exists a pair of integers such that .

Is there a sufficiently fast method for finding this pair, or is the problem of writing as a sum of squares considered to be a hard problem like "Integer Factorization"?

Printable View

- Jun 27th 2010, 12:42 PMjamixWriting p = x^2 + y^2
We know that for primes , there exists a pair of integers such that .

Is there a sufficiently fast method for finding this pair, or is the problem of writing as a sum of squares considered to be a hard problem like "Integer Factorization"? - Jun 27th 2010, 12:48 PMchiph588@
My understanding is it's hard to find .

This is because in , where are prime.

So this is a factoring problem like you mentioned. - Jun 27th 2010, 07:19 PMjamix
On the surface of it, I agree. However lets not be too quick to judge.

I've been thinking about this somewhat and we know that for primes we can quickly solve the equation .

For instance, then

On the other hand, if then

Rearranging the variables if necessary, lets suppose

Since we know the value of , the problem comes down to choosing an integer such that is fairly small.

Having done the above, we have for some integer which isn't too large.

On the other hand using the identity

We know there exist values such that as k can only be product of primes of the form to an even exponent (Do you know why?).

Thus if we can express k as a sum of squares, it will follow from the above identity that and the pair can be found by solving the following two linear Diophantine equations:

and

I believe solving for the two simultaneous Diophantine equations in this case is trivial, but I'm a little tired to fill in the details at the moment.

.................................................. ...

Reflecting back on everything I just wrote, I think the real problem is finding an integer such that is fairly small. As I've right now, I'm not sure of any obvious way to do this. If it is a nontrivial problem, then I would echo your line in that this is due to factorization of integers in to be an intractable problem (ie no fast methods to obtain solutions). - Jun 27th 2010, 08:46 PMChandru1
If are relatively prime and if , then

- Jun 27th 2010, 10:45 PMjamix
Yeah. In fact even for we have that if and .

........................................

I think one can solve this problem using a non-deterministic algorithm. If one removes the restriction that necessarily. I have one kinda worked out on paper, but its messy. I'll post it soon. - Jun 28th 2010, 12:03 AMBacterius
Let be an odd prime. Let for any , that is, .

Then the solutions are given by

This can be computed using the Tonelli-Shanks algorithm, a polynomial time algorithm that yields square roots modulo a prime number. - Jun 28th 2010, 04:04 AMtonio
- Jun 28th 2010, 05:22 AMBacterius
- Jun 28th 2010, 12:35 PMjamix
Thanks for the effort, but I wasn't trying to find such that . This is trivial once we have solved since for any nonzero element , if we choose , it follows that since .

The above only applies for primes of the form . These are the primes I'm interested in since if and only if . Trying to write these primes as sums of squares was what I was trying to accomplish in this thread, alas yet to no avail.