[GAP Forum] Different TwoSquares algorithm for large input?

[Asst. Prof. Dmitrii (Dima) Pasechnik]

Dear Richard,

Sage includes a number of number-theoretic systems that should be
much better than GAP in factoring, e.g. PARI.
That's, if you like, the whole purpose of Sage, to make the best tool
available for each particular job.

You can also install extra GAP packages into your Sage installation,
although this is not very straightforward, if this includes compiling
executables.

Best,
Dmitrii

On 26 July 2010 22:16, Richard Graham <rickhg12hs at gmail.com> wrote:
> 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
>>
>>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>



--
Dmitrii Pasechnik
-----
DISCLAIMER: Any text following this sentence does not constitute a
part of this message, and was added automatically during transmission.

CONFIDENTIALITY: This email is intended solely for the person(s) named and may be confidential and/or privileged. If you are not the intended recipient, please delete it, notify us and do not copy, use, or disclose its content. Thank you.

Towards A Sustainable Earth: Print Only When Necessary