[GAP Forum] Different TwoSquares algorithm for large input?

[Max Horn]

Dear Richard, dear Forum,

Am 29.07.2010 um 06:15 schrieb Richard Graham:

> Dear Dmitrii,
> 
> Thanks for the tip on enhancing my Sage install.
> 
> However, all the factoring power my little laptop can produce won't factor
> an RSA challenge number in any reasonable time, but the four squares
> algorithm at:
> 
> http://www.alpertron.com.ar/FSQUARES.HTM
> 
> ... can produce the sums of squares in less than a few seconds.

Of course. Two get a sum of three or four squares, you don't need to factor. The site you refer to mentions that explicitly.

So, if you just want to write a number as sum of four squares (where 0^2 is allowed as a summand), then you do not have to use TwoSquares, but rather should use an algorithm for that. 

Darin Alpern even kindly provides the source code for what he does on his website, as well as alink to a page which explains how the four squares applet works: <http://www.alpertron.com.ar/4SQUARES.HTM>, scroll to the bottom for the factorization free approach.


> 
> My real question is about the TwoSquares algorithm. Is there a better (or
> perhaps extended/augmented) TwoSquares algorithm that Gap could use that
> would extend its range of usefulness?

To the best of my knowledge, no, factorization is required to solve this. The two squares problem is considerably harder than the four squares problem.


Cheers,
Max