[GAP Forum] Different TwoSquares algorithm for large input?

[Richard Graham]

Thanks for your response.

I suppose relying on integer factorization is the limiting factor (pun
intended).  Sage does not appear to include Gap's factint, but still,
factorization of large numbers can be difficult.

Sage's four_squares function also relies on Gap's TwoSquares function, so it
too is limited.

I noticed that the four square problem is solved without factorization at:

http://www.alpertron.com.ar/FSQUARES.HTM

... and it can take very large inputs (I tried numbers greater than 2^1000).

I am wondering if the TwoSquares problem can be solved without integer
factorization.

Cheers!
Richard

On Mon, Jul 26, 2010 at 4:27 AM, Stephen Linton <sal at mcs.st-andrews.ac.uk>wrote:

> How large are your inputs? For me the existing algorithms seems to work
> quite well for really quite large numbers, limited mainly by integer
> factorisation.
> One obvious question is therefore: do you have the factint GAP package
> installed? It's part of the standard GAP distribution, but I don't know
> about SAGE.
>
> You can check with the GAP command
>
> InstalledPackageVersion("factint");
>
> which will give a version number or "fail.
>
>        Steve Linton
>
> On 26 Jul 2010, at 00:51, Richard Graham wrote:
>
> > I use Sage for some recreational mathematics, which in turn uses Gap.  I
> > would like to use the TwoSquares function with inputs that are large. Is
> > there perhaps another algorithm that could be used to handle large input?
> > Thanks.
> > _______________________________________________
> > Forum mailing list
> > Forum at mail.gap-system.org
> > http://mail.gap-system.org/mailman/listinfo/forum
>
>