msieve addition to sage

[jeffblakeslee]

Hello all,

Please consider voting on the addition of msieve to sage. This
includes an interface file and an .spkg. Msieve, by Jason
Papadopoulos, should increase the integer factorization functionality
of Sage. I'll quote the words of Jason in the Readme file by way of
explanation:

"There are plenty of algorithms for performing integer factorization.
The Msieve library implements most of them from scratch, and relies
on
optional external libraries for the rest of them. Trial division and
Pollard Rho is used on all inputs; if the result is less than 25
digits
in size, tiny custom routines do the factoring. For larger numbers,
the
code
switches to the GMP-ECM library and runs the P-1, P+1 and ECM
algorithms,
expending a user-configurable amount of effort to do so. If these do
not
completely factor the input number, the library switches to the heavy
artillery. Unless told otherwise, Msieve runs the self-initializing
quadratic
sieve algorithm, and if this doesn't factor the input number then
you've
found a library problem. If you know what you're doing, Msieve also
contains
a complete implementation of the number field sieve, that has helped
complete
some of the largest public factorization efforts known."

and

"To be as fast as possible. I claim (without proof) that for
completely factoring general inputs between 40 and 100 digits in size,
Msieve is faster than any other code implementing any other algorithm."

[William Stein]

On Thu, Feb 19, 2009 at 12:48 AM, jeffblakeslee <jeff...@gmail.com> wrote:
>
> Hello all,
>
> Please consider voting on the addition of msieve to sage. This
> includes an interface file and an .spkg.

Where is the interface file and spkg posted? Did you forget to include
a link in this email?

-- William

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[mabshoff]

On Feb 19, 12:51 am, William Stein <wst...@gmail.com> wrote:

> On Thu, Feb 19, 2009 at 12:48 AM, jeffblakeslee <jeffb...@gmail.com> wrote:
>
> > Hello all,
>
> >    Please consider voting on the addition of msieve to sage.  This
> > includes an interface file and an .spkg.
>
> Where is the interface file and spkg posted?  Did you forget to include
> a link in this email?

http://trac.sagemath.org/sage_trac/ticket/5310

[William Stein]

On Thu, Feb 19, 2009 at 12:54 AM, mabshoff <mabs...@googlemail.com> wrote:
>
>
>
> On Feb 19, 12:51 am, William Stein <wst...@gmail.com> wrote:
>> On Thu, Feb 19, 2009 at 12:48 AM, jeffblakeslee <jeffb...@gmail.com> wrote:
>>
>> > Hello all,
>>
>> > Please consider voting on the addition of msieve to sage. This
>> > includes an interface file and an .spkg.
>>
>> Where is the interface file and spkg posted? Did you forget to include
>> a link in this email?
>
> http://trac.sagemath.org/sage_trac/ticket/5310
>

The spkg there doesn't install on anything. Could Jeff please fix it,
then repost here.

William

[Michel]

+1

The default factor command in sage is rather slow.

[mabshoff]

On Feb 20, 1:37 am, Michel <michel.vandenbe...@uhasselt.be> wrote:
> +1

+1 from me too once we sort out all the small issues like building,
etc. License as well as build requirements are met for inclusion into
Sage. It is also certainly fast :)

> The default factor command in sage is rather slow.

Note that there is mpQS from FLINT and the goal is to have factor be
clever and pick the best code depending on the size of the integer to
factor, i.e. pari, mpQS and msieve once it makes it in Sage. We plan
to also use mpQS (it is already in Sage, but not installed yet) but
see

http://trac.sagemath.org/sage_trac/ticket/5238

for the mpQS ticket and

http://trac.sagemath.org/sage_trac/ticket/1145

for a high level factorization strategy. If anyone wants to work on
this let us know :p

And for mpQS vs. msieve Bill Hart has some numbers:

[quote]
Anything over about 75 digits will be much slower on mpQS than on
msieve, due to the fact that the latter implements the double large
prime variant and I don't. But the time for the second factorization
is 15min 35s in mpQS.

Here are some other times:

msieve mpQS

2891670903938774131753:

0.010s 0.000s

7223934149780053552120237:

0.020s 0.020s

10890325463531930685071186191:

0.070s 0.020s

22746696815551279204773065179537:

0.100s 0.040s

34714945933810757311137622885134169:

0.110s 0.050s

10173256651176584336392947473501127227:

0.130s 0.080s

13018279488865181129955874562185134688337:

0.200s 0.090s

22301677236991560444759885102875349454660651:

0.230s 0.210s

8941543217242472708029937221739551760158967009:

0.340s 0.280s

6399059753136044767573853384689913264328520902553:

0.570s 1.740s

25506563753254047681462924229892337031031187330409537:

1.050s 1.250s

37987772559424160043450717911696894399547208398069213931:

1.930s 2.520s

So for smaller numbers, mpQS is faster than msieve. I just haven't
worked on speeding it up for numbers of 75 digits and more.
[end quote]


This might be worth adding to the msieve ticket and I will do so
shortly.

Cheers,

Michael

[jeffblakeslee]

I have updated the spkg at

http://trac.sagemath.org/sage_trac/ticket/5310


On Feb 19, 3:34 pm, William Stein <wst...@gmail.com> wrote: