Welcome to MathOverflow

Question

29

5

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 factorisation.

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.)

flag	asked Mar 9 2011 at 18:56 H A Helfgott 3,102●9●31

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). – Emil Jeřábek Mar 9 2011 at 19:07

1

@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. – David Loeffler Mar 9 2011 at 19:15

8

"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! – David Speyer Mar 9 2011 at 19:16

2

@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. – GH Mar 9 2011 at 19:24

1

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. – Chris Wuthrich Mar 9 2011 at 19:39

show 1 more comment

Charles · Answer 1 · 2011-03-09 19:28:17Z UTC

9

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.

edited Mar 9 2011 at 19:28

answered Mar 9 2011 at 19:20

Charles
4,159●8●26

	Please explain - how would you use Coppersmith's algorithm? What information would you be assuming, precisely? – H A Helfgott Mar 12 2011 at 20:12
	?? 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.) – Charles Mar 13 2011 at 3:45
	See also Tao's answer mathoverflow.net/questions/3820/… . – Charles Mar 13 2011 at 3:50

Max Alekseyev · Answer 2 · 2011-03-09 19:51:56Z UTC

7

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

answered Mar 9 2011 at 19:51

Max Alekseyev
1,669●4●9

8

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. – Peter Shor Mar 9 2011 at 23:32

1

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. – Emil Jeřábek Mar 10 2011 at 11:02

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. – Max Alekseyev Jul 19 2011 at 15:45

Kevin O'Bryant · Answer 3 · 2011-06-26 02:16:21Z UTC

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.

Testing whether an integer is the sum of two squares

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.