#5310: Add an spkg to Sage for Msieve factoring program
-------------------------------------+-------------------------------------
Reporter: jblakeslee | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: packages: | Resolution:
experimental | Merged in:
Keywords: msieve, | Reviewers: David Kirkby, Leif
factorization | Leonhardy, Paul Zimmermann
Authors: André Apitzsch | Work issues:
Report Upstream: N/A | Commit:
Branch: | 1d4525f85e2ec7fd412c97898c475e12cce58b91
u/kartikv/5310-msieve | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by kartikv):
* status: needs_work => needs_review
* component: packages: optional => packages: experimental
* branch: => u/kartikv/5310-msieve
* commit: => 1d4525f85e2ec7fd412c97898c475e12cce58b91
* work_issues: does not work on 32-bit, Solaris not handled well, no spkg-
check file =>
Old description:
> This addition of Msieve will hopefully enhance Sage's Integer
> Factorization ability for all integers of a reasonable size, and provide
> the opportunity for users to utilize the Number Field Sieve.
>
> spkg located:
>
> http://309codesign.com/code/
>
> An explanation of Msieve from its documentation:
> "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."
>
> ----
>
> '''New spkg:''' [http://trac.sagemath.org/sage_trac/raw-
> attachment/ticket/5310/msieve-1.49.p0.spkg]
>
> '''Apply:'''
> 1. [attachment:trac_5310_msieve_149.patch]
> to the Sage library.
New description:
This addition of Msieve will hopefully enhance Sage's Integer
Factorization ability for all integers of a reasonable size, and provide
the opportunity for users to utilize the Number Field Sieve.
http://309codesign.com/code/
An explanation of Msieve from its documentation:
"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."
----
Upstream tarball: http://downloads.sourceforge.net/msieve/msieve149.tar.gz
(rename to msieve-1.49.tar.gz)
--
Comment:
Changed to an experimental package in order to get into Sage for 64-bit
systems, seems to work fine on those. Reasonably tested with good speed
and documentation for main function provided, may be useful to include
additional doctests.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=6e11d0cc5b7aa394bb09dc2403b69bb61793800f
6e11d0c]||{{{trac 5310: msieve interface}}}||
||[http://git.sagemath.org/sage.git/commit/?id=1d4525f85e2ec7fd412c97898c475e12cce58b91
1d4525f]||{{{msieve wrapper for sage}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/5310#comment:40>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
