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, 2017 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, 2017 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, 2017 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, 2018 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, 2019 at 14:36

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .