# Thread: Writing p = x^2 + y^2

1. ## Writing p = x^2 + y^2

We know that for primes $p \equiv 1 mod(4)$, there exists a pair of integers $(x,y)$ such that $x^2 + y^2 = p$.

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

2. My understanding is it's hard to find $(x,y)$.

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

So this is a factoring problem like you mentioned.

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

This is because in $\mathbb{Z}[i]$, $p=(x+iy)(x-iy)$ where $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 $p = 1 + 4 \cdot k$ we can quickly solve the equation $x^2 + 1 \equiv 0 mod(p)$.

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

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

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

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

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

On the other hand using the identity $(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 $(a_1,b_1)$ such that $a_1^{2} + b_1^{2} = k$ as k can only be product of primes of the form $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 $p = a_2^{2} + b_2^{2}$ and the pair $(a_2,b_2)$ can be found by solving the following two linear Diophantine equations:

$a_1 \cdot a_2 + b_1 \cdot b_2 = a$ and $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 $a < \sqrt{p}$ such that $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 $\mathbb{Z}[i]$ to be an intractable problem (ie no fast methods to obtain solutions).

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

5. Originally Posted by Chandru1
If $p,c \in \mathbb{Z}[i]$ are relatively prime and if $x^{2}+y^{2}=cp$, then $p=a^{2}+b^{2}$
Yeah. In fact even for $p,c \in \mathbb{Z}$ we have that $p = a^2 + b^2$ if $p \cdot c = x^2 + y^2$ and $gcd(p,c) = 1$.

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

I think one can solve this problem using a non-deterministic algorithm. If one removes the restriction that $a < \sqrt{p}$ necessarily. I have one kinda worked out on paper, but its messy. I'll post it soon.

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

Then the solutions are given by $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.

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

Then the solutions are given by $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: $x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}=\pm\sqrt{kp-y^2}\!\!\pmod p$

Tonio

8. Originally Posted by tonio
Slightly simpler: $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

Also, you need $kp - y^2$ to be a quadratic residue modulo $p$. But this is not an issue since there are exactly 50% of quadratic residues modulo any odd prime $p$

9. Thanks for the effort, but I wasn't trying to find $(x,y)$ such that $x^2 + y^2 \equiv 0$. This is trivial once we have solved $x^2 + 1 \equiv 0$ since for any nonzero element $a$, if we choose $b \equiv a \cdot x^{-1}$, it follows that $a^2 + b^2 \equiv 0$ since $x^{-1} \equiv -x$.

The above only applies for primes of the form $1 + 4 \cdot k$. These are the primes I'm interested in since $p = x^2 + y^2$ if and only if $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.