# Sum of two squares problem

I would like to know if there is any existing research on the following problem:

$$\text{For }a, b \in \mathbb Z \text{, given }n = a^2 + b^2, \text{output }a, b$$.

Searching for "sum of squares", "quadratic sum", "two squares", etc. on eprint did not return any related results that I could find. The problem itself may have been given a particular name, but if it has I don't know it and so I can't search for it.

I did a search on some of the math stackexchange sites and:

The naive algorithm for solving the problem runs in time $O(\operatorname{sqrt}(n))$ by simply guessing all possible values for $a$ up to $\operatorname{sqrt}(n)$, squaring them, subtracting $a^2$ from $n$, then checking whether the result is a perfect square.

I would like to know any of the following:

• Is there pre-existing research on the problem that I can consult
• Does the problem have a name other than "Sum of two squares"
• Can we prove that the problem is either "hard" or "easy", for the usual definitions of the terms on a hard instance of the problem (e.g. one where $n$ is not a prime congruent to $1 \bmod 4$)
• Maybe looking at the Rabin-Miller algorithm? It decomposes an arbitrary integer into a sum of 4 squares and runs in randomized polytime, it can probably be adapted to your problem. – Geoffroy Couteau Sep 1 '18 at 22:29
• @GeoffroyCouteau Thanks for the suggestion - did you by chance intend to type Rabin-Shallit algorithm rather than Rabin-Miller? The only hits for Rabin-Miller I can find are for the well known primality test, while Rabin-Shallit fits the description you give accurately. – Ella Rose Sep 1 '18 at 22:50
• Sorry, yes I meant Rabin-Shallit - was writing from memory on my phone – Geoffroy Couteau Sep 1 '18 at 22:52
• Your question is a standard problem in algebraic number theory. For instance, see here The question would better fit to the Mathematics Stackexchange forum. – Rainer Urian Sep 4 '18 at 18:16
• Tangentially related, a solution $a, b$ is not always unique, e.g. $1^2 + 8^2 = 65$ and $4^2 + 7^2 = 65$. This means using the function as some sort of trapdoor may not be feasible since recovering $a, b$ from $N$ may not give back the same $a, b$ used to initially compute $N$. – puzzlepalace Sep 4 '18 at 22:09

A well-known result is $gcd(t+i, n)$ over Gaussian numbers where $t$ is a square root of (-1) modulo $n$. The reason is $t^2 = -1 \pmod{n}$ equivalent to $n | (t+i)(t-i)$ over $Z[i]$. Real and img components of this $gcd()$ are the squares.
• Is there an efficient algorithm for finding $t$ such that $t^2 \equiv -1 \pmod n$? I have to admit I can't seem to think of how to compute $t$ off hand. – Ella Rose Sep 4 '18 at 18:39
• So when $n$ is prime you can find such a $t$ by picking random $x$ until you find $x^{\frac{(n - 1)}{2}} \equiv -1 \bmod n$, then $t = x^{\frac{(n - 1)}{4}} \bmod n$. So it appears when $n$ is composite you'd need to know the factorization and then apply some modified form of the above. I will probably accept this as the answer, Thanks! – Ella Rose Sep 5 '18 at 2:37
• @EllaRose If you could find such a $t$ and you could solve the problem in the question, then you could easily transform $a,b,t$ into a solution for $x^2 -y^2=0$ mod $n$ and thus factor. The problems are connected, and this might not be computable. But we also have to keep in mind, $-1$ might not be a quadratic residue mod $n$. – tylo Sep 5 '18 at 8:11