# 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 may have been given a particular name, but if it has, I don't know it, so I can't search for it.

I searched some of the math stackexchange sites and:

• There appears to be a relation between a decisional variant of the problem and factoring. Namely, "determine whether or not $$n$$ is a sum of two squares" can be solved with knowledge of the factorization of $$n$$.
• I found a result that allows the problem to be solved efficiently when $$n$$ is a prime congruent to $$1 \bmod 4$$.

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. Commented Sep 1, 2018 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. Commented Sep 1, 2018 at 22:50
• Sorry, yes I meant Rabin-Shallit - was writing from memory on my phone Commented Sep 1, 2018 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. Commented Sep 4, 2018 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$. Commented Sep 4, 2018 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. Commented Sep 4, 2018 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! Commented Sep 5, 2018 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
Commented Sep 5, 2018 at 8:11

theorem there is the following sieve :

Let $$p,k>1,c,d$$ be integers then we have : $$p=4k^2+1 \operatorname{is prime iff} p\neq c^2+d^2,c>1,d>1$$

$$\implies$$ https://math.stackexchange.com/questions/719700/if-a-prime-can-be-expressed-as-sum-of-square-of-two-integers-then-prove-that-th

The other case :

see : On numbers which are the sum of two squares - The Euler Archive http://eulerarchive.maa.org/docs/translations/E228en.pdf

For example :

If someone ask you to find quickly if $$257$$ is a prime number use the sieve above .

https://en.m.wikipedia.org/wiki/Pierpont_prime $$v=0$$

As the sum is symmetric and homogeneous we need less term than in taking divisor and square roots of the prime.

There are other example of Diophantine equation like Brocard's problem stating :

Let $$n>7,m$$ be integers then we have :

$$n!+1\neq m^2$$

A proof From the Book for a partial proof of the Brocard-Ramanujan problem (gave at the end) :

Here $$k,n,m$$ are strictly positive integers .

Lemma 1:

$$A=(n(n+1)+1)^2-1=(n(n+1))(n(n+1)+2)$$

Proof :

$$a^2-b^2=(a-b)(a+b)$$

Now we can say that as $$(n(n+1)+2)$$ is even :

$$(n(n+1)+1)!=kA$$

Or :

$$(n(n+1)+1)!+1=1+kA$$

Now we equalize to :

$$1+kA=n^{2m}$$

An evidence say we can factor to this form :

$$(n+1)(k(F(n))+G(n))=0$$

$$F(n)$$ is almost geometric series $$(n^3+n^2+2n)$$ of order $$3$$ and $$G(n)$$ is an alternating geometric series $$(-n^m+\cdots+1)$$ .

Isolating $$k$$ we have as unique solution :

$$n=1$$

Because it's always a rational number NOT an integers for $$k$$.

It seems sufficiently balanced to be interesting enought .