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][1], 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][2]). To be specific, $F_{1049}$ is a sum of two squares, but has not yet been factored. [1]: http://mathoverflow.net/questions/67601/which-fibonacci-numbers-are-the-sum-of-two-squares [2]: http://mersennus.net/fibonacci/