[GAP Forum] Different TwoSquares algorithm for large input?

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

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?

Regards,
Richard

On Wed, Jul 28, 2010 at 11:17 AM, Asst. Prof. Dmitrii (Dima) Pasechnik <
dima at ntu.edu.sg> wrote:

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