Sum of two squares problem

Question

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$)

Answer 1

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.

Answer 2

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$$

Partial progress for 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+1)^{2m}$$

An evidence say we can factor to this form :

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

The role of the binomial coefficient is important here .

The number of solution are limited or not existing due to Faltings/Siegel theorem .

It seems sufficiently balanced to be interesting enought .