#1145: high-level strategy for integer factorization
---------------------------+------------------------------------------------
Reporter: zimmerma | Owner: aapitzsch
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-4.6.2
Component: factorization | Resolution:
Keywords: | Author:
Upstream: N/A | Reviewer:
Merged: | Work_issues:
---------------------------+------------------------------------------------
Changes (by aapitzsch):
* milestone: sage-wishlist => sage-4.6.2
Old description:
> I propose the following strategy for factor(integer):
>
> 1. do trial division by all primes up to say 1000. This can be done
> efficiently by a single gcd with the product of all those primes.
> 2. use GMP-ECM, starting from say B1=100, and increasing B1 by sqrt(B1)
> at each step, until one reaches the _recommended_B1_list value which
> corresponds to 1/3 of the size of the number to be factored. Thus for a
> 90-digit input, one will stop at B1=250000.
> 3. try GMP-ECM P-1 and P+1 with respectively 9*B1 and 3*B1 where B1 is
> the last value tried for ECM. The corresponding cost of those runs will
> be approximately the same as the last ECM curve, thus this will not slow
> down the average computation, and might find a few factors.
> 4. run MPQS or GNFS. You might want to issue a warning to the user (if
> called from toplevel) at that time.
>
> == Apply ==
> 1. #5310
> 1. #5945
> 1. [attachment:trac_1145_integer_factorization.patch]
> 1. [attachment:trac_1145_cunningham_warning.patch]
New description:
I propose the following strategy for factor(integer):
1. do trial division by all primes up to say 1000. This can be done
efficiently by a single gcd with the product of all those primes.
2. use GMP-ECM, starting from say B1=100, and increasing B1 by sqrt(B1)
at each step, until one reaches the _recommended_B1_list value which
corresponds to 1/3 of the size of the number to be factored. Thus for a
90-digit input, one will stop at B1=250000.
3. try GMP-ECM P-1 and P+1 with respectively 9*B1 and 3*B1 where B1 is
the last value tried for ECM. The corresponding cost of those runs will be
approximately the same as the last ECM curve, thus this will not slow down
the average computation, and might find a few factors.
4. run MPQS or GNFS. You might want to issue a warning to the user (if
called from toplevel) at that time.
== Apply ==
1. #5310
1. #5945
1. #10623
1. [attachment:trac_1145_integer_factorization.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/1145#comment:30>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
