Writing p = x^2 + y^2

• Jun 27th 2010, 11:42 AM
jamix
Writing p = x^2 + y^2
We know that for primes $\displaystyle p \equiv 1 mod(4)$, there exists a pair of integers $\displaystyle (x,y)$ such that $\displaystyle x^2 + y^2 = p$.

Is there a sufficiently fast method for finding this pair, or is the problem of writing $\displaystyle p$ as a sum of squares considered to be a hard problem like "Integer Factorization"?
• Jun 27th 2010, 11:48 AM
chiph588@
My understanding is it's hard to find $\displaystyle (x,y)$.

This is because in $\displaystyle \mathbb{Z}[i]$, $\displaystyle p=(x+iy)(x-iy)$ where $\displaystyle x\pm iy$ are prime.

So this is a factoring problem like you mentioned.
• Jun 27th 2010, 06:19 PM
jamix
Quote:

Originally Posted by chiph588@
My understanding is it's hard to find $\displaystyle (x,y)$.

This is because in $\displaystyle \mathbb{Z}[i]$, $\displaystyle p=(x+iy)(x-iy)$ where $\displaystyle x\pm iy$ are prime.

So this is a factoring problem like you mentioned.

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 $\displaystyle p = 1 + 4 \cdot k$ we can quickly solve the equation $\displaystyle x^2 + 1 \equiv 0 mod(p)$.

For instance, $\displaystyle if p \equiv 5 mod(8)$ then $\displaystyle x \equiv 2^{\frac{p-1}{4}} mod(p)$

On the other hand, if $\displaystyle p = a^2 + b^2$ then $\displaystyle a \cdot b^{-1} \equiv +x, -x mod(p)$

Rearranging the variables $\displaystyle (a,b)$ if necessary, lets suppose $\displaystyle a \cdot b^{-1} \equiv +x mod(p)$

Since we know the value of $\displaystyle x$, the problem comes down to choosing an integer $\displaystyle a < \sqrt{p}$ such that $\displaystyle a \cdot x^{-1} mod(p)$ is fairly small.

Having done the above, we have $\displaystyle a^2 + b^2 = k \cdot p$ for some integer $\displaystyle k$ which isn't too large.

On the other hand using the identity $\displaystyle (a_1^{2} + b_1^{2}) \cdot (a_2^{2} + b_2^{2}) = (a_1 \cdot a_2 + b_1 \cdot b_2)^{2} + (a_1 \cdot b_2 - b_1 \cdot a_2)^{2}$

We know there exist values $\displaystyle (a_1,b_1)$ such that $\displaystyle a_1^{2} + b_1^{2} = k$ as k can only be product of primes of the form $\displaystyle 3 + 4s$ 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 $\displaystyle p = a_2^{2} + b_2^{2}$ and the pair $\displaystyle (a_2,b_2)$ can be found by solving the following two linear Diophantine equations:

$\displaystyle a_1 \cdot a_2 + b_1 \cdot b_2 = a$ and $\displaystyle a_1 \cdot b_2 -b_1 \cdot a_2 = b$

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 $\displaystyle a < \sqrt{p}$ such that $\displaystyle a \cdot x^{-1} mod(p)$ 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 $\displaystyle \mathbb{Z}[i]$ to be an intractable problem (ie no fast methods to obtain solutions).
• Jun 27th 2010, 07:46 PM
Chandru1
If $\displaystyle p,c \in \mathbb{Z}[i]$ are relatively prime and if $\displaystyle x^{2}+y^{2}=cp$, then $\displaystyle p=a^{2}+b^{2}$
• Jun 27th 2010, 09:45 PM
jamix
Quote:

Originally Posted by Chandru1
If $\displaystyle p,c \in \mathbb{Z}[i]$ are relatively prime and if $\displaystyle x^{2}+y^{2}=cp$, then $\displaystyle p=a^{2}+b^{2}$

Yeah. In fact even for $\displaystyle p,c \in \mathbb{Z}$ we have that $\displaystyle p = a^2 + b^2$ if $\displaystyle p \cdot c = x^2 + y^2$ and $\displaystyle gcd(p,c) = 1$.

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

I think one can solve this problem using a non-deterministic algorithm. If one removes the restriction that $\displaystyle a < \sqrt{p}$ necessarily. I have one kinda worked out on paper, but its messy. I'll post it soon.
• Jun 27th 2010, 11:03 PM
Bacterius
Let $\displaystyle p$ be an odd prime. Let $\displaystyle x^2 + y^2 \equiv 0 \pmod{p}$ for any $\displaystyle x, y \in \mathbb{Z}/p\mathbb{Z}$, that is, $\displaystyle x^2 + y^2 - kp = 0$.

Then the solutions are given by $\displaystyle x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}$
This can be computed using the Tonelli-Shanks algorithm, a polynomial time algorithm that yields square roots modulo a prime number.
• Jun 28th 2010, 03:04 AM
tonio
Quote:

Originally Posted by Bacterius
Let $\displaystyle p$ be an odd prime. Let $\displaystyle x^2 + y^2 \equiv 0 \pmod{p}$ for any $\displaystyle x, y \in \mathbb{Z}/p\mathbb{Z}$, that is, $\displaystyle x^2 + y^2 - kp = 0$.

Then the solutions are given by $\displaystyle x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}$
This can be computed using the Tonelli-Shanks algorithm, a polynomial time algorithm that yields square roots modulo a prime number.

Slightly simpler: $\displaystyle x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}=\pm\sqrt{kp-y^2}\!\!\pmod p$

Tonio
• Jun 28th 2010, 04:22 AM
Bacterius
Quote:

Originally Posted by tonio
Slightly simpler: $\displaystyle x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}=\pm\sqrt{kp-y^2}\!\!\pmod p$

Indeed, I didn't spot that, thanks (Nod)

Also, you need $\displaystyle kp - y^2$ to be a quadratic residue modulo $\displaystyle p$. But this is not an issue since there are exactly 50% of quadratic residues modulo any odd prime $\displaystyle p$ (Cool)
• Jun 28th 2010, 11:35 AM
jamix
Thanks for the effort, but I wasn't trying to find $\displaystyle (x,y)$ such that $\displaystyle x^2 + y^2 \equiv 0$. This is trivial once we have solved $\displaystyle x^2 + 1 \equiv 0$ since for any nonzero element $\displaystyle a$, if we choose $\displaystyle b \equiv a \cdot x^{-1}$, it follows that $\displaystyle a^2 + b^2 \equiv 0$ since $\displaystyle x^{-1} \equiv -x$.

The above only applies for primes of the form $\displaystyle 1 + 4 \cdot k$. These are the primes I'm interested in since $\displaystyle p = x^2 + y^2$ if and only if $\displaystyle p = 1 + 4 \cdot k$. Trying to write these primes as sums of squares was what I was trying to accomplish in this thread, alas yet to no avail.