[GAP Forum] Different TwoSquares algorithm for large input?

[Richard Graham]

Max,


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

Factorization is required.

Ok, thanks!

Richard


On Thu, Jul 29, 2010 at 4:00 AM, Max Horn <max at quendi.de> wrote:

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