11
$\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$)
$\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$ 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$ 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$ 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$ Sep 4, 2018 at 22:09

2 Answers 2

2
$\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.

$\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
1
$\begingroup$

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

Sketch of proof :

Using Fibonacci's identity :

$$\left(n^{2}+1\right)\left(\left(n+1\right)^{2}+1\right)=\left(n\left(n+1\right)+1\right)^{2}+1$$

Then if $\left(n+1\right)^{2}+1$ is not a prime number then we conclude that :

$$\gcd((n(n+1)+1)!+1,(n(n+1)+1)^2+1)=1$$

If so :

$$(n(n+1)+1)!+1=1+k((n(n+1)+1)^2+1)$$

Now we jump to $n(n+1)+1$ to $2n(2n+1)+1$ showing using Bertrand's postulate that there is a prime and so $k\neq a^2,a\in N$ remains to show that :

$$1+k((n(n+1)+1)^2+1)\neq p^2,p\in N$$

Which can be proved using Hasse-Minkowski's theorem on quadratics and invariant .

Also see

Angular Momentum

Where we have the inequality :

$$\lambda\geq m^2$$



For physical meaning we have the Euler's proof of Fermat sum of two square theorem available on wikipedia which is as a part :

$$\frac{a^{2}+b^{2}}{p^{2}+q^{2}}=\left(\frac{ap+bq}{p^{2}+q^{2}}\right)^{2}+\left(\frac{aq-bp}{p^{2}+q^{2}}\right)^{2}$$

Now use the Harnack's inequality also available on wikipedia :

$$\frac{R-r}{R+r}f\left(x_{0}\right)\leq f\left(x\right) $$

Where we are in the case $n=2$ if $f$ is continuous on the closed ball and harmonic on its interior,$\left|x-x_{0}\right|=r<R$

Remark :

$$\ln\left(\left(m^{2}+n^{2}\right)!\right)-\ln\left(\left(m^{2}+n^{2}-1\right)!\right)-\ln\left(\left(m^{2}+n^{2}\right)\right)=0$$

Where $m,n\in N^+$ as $\ln(x^2+y^2)$ is a harmonic function it shows Brocard's problem have no solution since the Brown's numbers cannot be write as the sum of two integer square .

Elliptic curve are widely use in cryptography and I think partial differential equation could be benefic

$\endgroup$
5

Your Answer

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

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