47
$\begingroup$

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares?

By "fast" here I mean polynomial time (i.e. time $O((\log n)^{O(1)})$). Note that I am interested only in whether the integer can be represented in such a way, not in how it is represented.

Since a fast algorithm is required, it will not do to use factorization.

It would be odd if this turned out to be harder than detecting primality, since prime numbers are rarer.

(This is a question that came up in a talk I just gave.)

Improve this question
$\endgroup$
7
  • $\begingroup$ I wouldn't expect detecting representable numbers to be substantially easier than computing such a representation. There is a probabilistic polynomial-time algorithm for finding these representations by Rabin and Shallit (dx.doi.org/10.1002/cpa.3160390713), but it only works for primes, which is the case you are not interested in (detecting whether a prime can be represented is trivial). $\endgroup$
    – Emil Jeřábek
    Commented Mar 9, 2011 at 19:07
  • 2
    $\begingroup$ @J.C. Ottem: "Polynomial time" in this context generally means "polynomial in the number of bits needed to represent the input", i.e. polynomial in $log(n)$. Harald makes this completely clear in the question. $\endgroup$
    – David Loeffler
    Commented Mar 9, 2011 at 19:15
  • 11
    $\begingroup$ "It would be odd if this turned out to be harder than detecting primality, since prime numbers are rarer." This intuition seems completely false to me. I can test whether $n$ is a power of $3$ is $O((\log n)^2)$, and that's a very rare condition! $\endgroup$
    – David E Speyer
    Commented Mar 9, 2011 at 19:16
  • 2
    $\begingroup$ @Emil: If a prime p is 1 mod 4 then a representation p=a^2+b^2 can be found in deterministic polynomial time. First use Schoof's algorithm (Math. Comp. 44 (1985), 483-494) to find a solution of x^2 = -1 mod p in polynomial time, then use the Euclidean algorithm in Gaussian integers to find a+bi=gcd(p,x+i) in polynomial time. $\endgroup$
    – GH from MO
    Commented Mar 9, 2011 at 19:24
  • 1
    $\begingroup$ An idea that does not help : It is equivalent to ask to check if the conic $x^2+y^2 = n$ has a rational solution. But unless I factor $n$, I would not know at which finitely many primes $p$ I have to check locally solubility. $\endgroup$
    – Chris Wuthrich
    Commented Mar 9, 2011 at 19:39

3 Answers 3

Reset to default
13
$\begingroup$

This problem is equivalent to detecting whether there is some prime $p\equiv3\pmod4$ dividing the number which is raised to an odd power. In the worst case, where the number is a large semiprime equivalent to 1 mod 4, this is almost surely as hard as FACTORIZATION. If it was easy, then it would give away the second-lowest bit in both prime factors of such numbers; if we had enough information of this type we could recover the factors via Coppersmith's algorithm.

Practically, check the number mod 4 (once you remove trailing 0s) and see if it's 3, then trial divide by small primes.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Please explain - how would you use Coppersmith's algorithm? What information would you be assuming, precisely? $\endgroup$
    – H A Helfgott
    Commented Mar 12, 2011 at 20:12
  • $\begingroup$ ?? You would CRT all the known residues together so that for one of the primes dividing n, p = r mod m. Then use Coppersmith to find numbers in that residue class which have a nontrivial gcd with n, recovering the factor. Isn't that a standard use of the algorithm? Of course you'd need a lot of information, but Coppersmith makes "a lot" a much smaller number than if the only available algorithm was testing numbers of the form r, r+m, r+2m, ... sequentially. (Obviously, if only a very small amount of information is known, general-purpose factorization is faster.) $\endgroup$
    – Charles
    Commented Mar 13, 2011 at 3:45
  • $\begingroup$ See also Tao's answer mathoverflow.net/questions/3820/… . $\endgroup$
    – Charles
    Commented Mar 13, 2011 at 3:50
  • $\begingroup$ @Charles How do you get second-lowest bit? $\endgroup$
    – VS.
    Commented Sep 29, 2019 at 21:17
  • $\begingroup$ @VS. No method is known or believed to exist. Tao has a post on his blog about this. $\endgroup$
    – Charles
    Commented Sep 29, 2019 at 23:38
12
$\begingroup$

There are situations where we know that a number is a sum of two squares although we do not know the factorization, and in fact know very little about the factors. This question, for example, notes that $F_{2k+1}=F_k^2+F_{k+1}^2$ (the $F_k$ are the Fibonacci numbers). On the flip side, though, while Fibonacci numbers are easier to factor than most, they are not trivial (I think Blair Kelly maintains a list of factors).

To be specific, $F_{1049}$ is a sum of two squares, but has not yet been factored.

Improve this answer
$\endgroup$
1
  • 13
    $\begingroup$ Ditto the various $2^{2^n}+1.$ $\endgroup$
    – Aaron Meyerowitz
    Commented Jun 26, 2011 at 2:49
8
$\begingroup$

The question is equivalent to testing whether -1 is a square modulo n. This corresponds to the quadratic residuosity problem which is supposedly computationally hard: http://en.wikipedia.org/wiki/Quadratic_residuosity_problem

Improve this answer
$\endgroup$
8
  • 10
    $\begingroup$ But is testing whether -1 is a square as hard as testing whether an arbitrary residue (with Jacobi symbol 1) is a square? Testing whether an arbitrary residue is a square is the supposedly hard quadratic residuosity problem. $\endgroup$
    – Peter Shor
    Commented Mar 9, 2011 at 23:32
  • 1
    $\begingroup$ To expand on Peter’s comment, the quadratic residuosity problem is supposed to be hard when $n$ is a Blum integer, in which case we know a priori that $-1$ is not a square. $\endgroup$
    – Emil Jeřábek
    Commented Mar 10, 2011 at 11:02
  • $\begingroup$ Why "quadratic residuosity problem is supposed to be hard when n is a Blum integer"? It is formulated for a generic composite number. A Blum integer would be a particular case of the problem. $\endgroup$
    – Max Alekseyev
    Commented Jul 19, 2011 at 15:45
  • $\begingroup$ Can you explain your equivalence? It is not directly equivalent as, for example, 45 is a sum of two squares but -1 is not a square modulo 45. $\endgroup$
    – ndkrempel
    Commented Oct 20, 2014 at 21:22
  • $\begingroup$ @ndkrempel: Strictly speaking, equivalence here is with being the sum of two coprime squares. For non-coprime squares, we can try to cancel all possible square factors of $n$ and then test if it becomes the sum of coprime squares. In particular, for $n=45$, we have that -1 is a square modulo $45/3^2=5$. $\endgroup$
    – Max Alekseyev
    Commented Oct 21, 2014 at 16:48

You must log in to answer this question.

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