Add an spkg to Sage for Msieve factoring program #5310
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.
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)
CC: @zimmermann6 @williamstein @boothby @nexttime @jpflori
Component: packages: experimental
Keywords: msieve, factorization
Work Issues: rebase
Author: André Apitzsch
Branch/Commit: u/kartikv/5310-msieve @ 1d4525f
Reviewer: David Kirkby, Leif Leonhardy, Paul Zimmermann
Issue created by migration from https://trac.sagemath.org/ticket/5310