[GAP Forum] Different TwoSquares algorithm for large input?

[Bill Allombert]

On Mon, Jul 26, 2010 at 03:16:48PM -0400, Richard Graham wrote:
> Thanks for your response.
> 
> I am wondering if the TwoSquares problem can be solved without integer
> factorization.

Well, if you can compute all the solutions of a^2+b^2=n and there is 
at least one solution with a and b coprimes, then you can factor n.

So solving the TwoSquares in general without integer factorization is higly unlikely.

Cheers,
Bill.