9
$\begingroup$

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$)
Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Geoffroy Couteau
    Sep 1, 2018 at 22:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ella Rose
    Sep 1, 2018 at 22:50
  • 2
    $\begingroup$ Sorry, yes I meant Rabin-Shallit - was writing from memory on my phone $\endgroup$
    – Geoffroy Couteau
    Sep 1, 2018 at 22:52
  • 1
    $\begingroup$ Your question is a standard problem in algebraic number theory. For instance, see here The question would better fit to the Mathematics Stackexchange forum. $\endgroup$
    – Rainer Urian
    Sep 4, 2018 at 18:16
  • $\begingroup$ 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$. $\endgroup$
    – puzzlepalace
    Sep 4, 2018 at 22:09

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ella Rose
    Sep 4, 2018 at 18:39
  • $\begingroup$ 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! $\endgroup$
    – Ella Rose
    Sep 5, 2018 at 2:37
  • 1
    $\begingroup$ @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$. $\endgroup$
    – tylo
    Sep 5, 2018 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.