[GAP Forum] Different TwoSquares algorithm for large input?

[Asst. Prof. Dmitrii (Dima) Pasechnik]

Dear Richard,
actually, Sage does include FactInt package, you just need to install
gap_packages spkg, e.g. as follows.

optional_packages() gives you the list of available optional packages:
e.g. on my 4.5.1 installation I get
sage: optional_packages()
(['database_gap-4.4.12.p0', 'gap_packages-4.4.12.p0'], ['ace-5.0.p0',
'biopython-1.54.p0', 'cbc-2.3.p2', 'cunningham_tables-1.0',
'database_cremona_ellcurve-20071019.p0', ...............])

the 1st list in the pair gives you already installed optional packages,
and the 2nd list - available, but not yet installed.
(for you probably the lists will look differently)

So you will need to run
install_package('gap_packages-4.4.12.p0')

after this is done you can just do
sage: gap.load_package("factint")
(same as LoadPackage("factint") in GAP)

and then it is loaded and you can e.g. do

sage: gap('FactorsTD(12^25+25^12)')
[ [ 13, 19, 727 ], [ 5312510324723614735153 ] ]

HTH,
Dmitrii

PS. Alex, I stand corrected, this package is available...

On 28 July 2010 15:40, Asst. Prof. Dmitrii (Dima) Pasechnik
<dima at ntu.edu.sg> wrote:
> 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.
>



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