Consider this problem:

PROBLEM: Given a positive integer $n > 1$. Question. Is $n$ the sum of two squares?

Actually there are three levels to the problem. The above is Level 1. The Level 2 Question is "Express $n$ as a sum of two squares". Level 3's Question is "Write down all ways in which $n$ is the sum of two squares".

I note that if one had an oracle that could factor numbers instantly, then all three of these problems can be solved in polynomial time. This means these problems are no harder than the Factorization Problem (FP)(Given n. Question: write down the factorization into primes of $n$). FP is in both NP and co-NP, so these problems are probably not NP-complete. What I am wondering is if any of these three problems is easier than FP, or maybe even polynomial (in P). If $n$ has a factor of the form $(4k-1)^p$ where $p$ is odd, then one can answer right away, "No" to all three problems. The problem comes with a number of the form $n$ = $4k+1$ for some positive $k$. Does it have factors of the form $4q-1$ or not? Can this be obtained somehow without having to factor $n$? Right now I can't think of a way.

  • $\begingroup$ Take a look at Cornacchia's Algorithm. $\endgroup$ – sharding4 Aug 3 '17 at 0:58
  • $\begingroup$ There are 4 ways to get a composite number of the form $N=4k+1$. As a product of $(4k_{1}-1)(4k_{2}-1)$, as a product of $(4k_{1}+1)(4k_{2}+1)$ and as a product of $(4k_{1}+3)(4k_{2}+3)$ and as a product of $(4k_{1}-3)(4k_{2}-3)$. So it's highly unlikely that there is a test that can tell if a number of the form $N=4k+1$ has a factor of the form $p=(4k-1)$. $\endgroup$ – user25406 Aug 3 '17 at 14:08
  • $\begingroup$ Here's an algorithm that calculate the sum of 2 squares of a given integer N without having to factor N. math.stackexchange.com/questions/1972771/… $\endgroup$ – user25406 Aug 3 '17 at 14:12
  • 1
    $\begingroup$ @user25406 many would say the $(4k_{1}-3)(4k_{2}-3)$ was essentially equivalent to the $(4k_{1}+1)(4k_{2}+1)$ type, and similarly with the other pair. So two ways, though your point is still valid $\endgroup$ – Henry Jul 27 '18 at 12:40
  • $\begingroup$ @Henry, I agree with you, that the product of two numbers of the form $(4k_1-3)(4k_2-3)$ is a number of the form $(4k+1)$. But somehow, those numbers don't have a sum of two squares. For example 3*7=21 doesn't. Somehow the final number knows about its origin but I never found a test that can differentiate between the two kinds of $(4k+1)$, the pure kind $(4k_1+1)(4k_2+1)$ and the other one $(4k_1-1)(4k_2-1)$. $\endgroup$ – user25406 Feb 10 '19 at 14:36

Getting two distinct answers can be used to compute an answer (if the representations are $a^2 + b^2 = c^2 + d^2 = n$, then use the Euclidean algorithm on $a+bi$ and $c+di$), so problem 3 is probably at least as hard as FP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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