high-level strategy for integer factorization

[zimmermann6]

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 9B1 and 3B1 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. Add an spkg to Sage for Msieve factoring program #5310
2. fastify factorization of inferior integers with flint #5945
3. Move integer factorization functions to a separate file #10623
4. attachment: trac_1145_integer_factorization.patch

CC: @jdemeyer @jpflori

Component: factorization

Issue created by migration from https://trac.sagemath.org/ticket/1145

[williamstein]

Description changed:

--- 
+++ 
@@ -1,12 +1,6 @@
 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.
+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.

[williamstein]

comment:3

Comments from some experts:

On 12/11/2007, Robert Bradshaw <robertwb@math.washington.edu> wrote:
> I don't have much expertise in the area, but it looks like a sound
> proposal to me. The trial division bound seems a bit low (and perhaps
> should be adjusted for the size of the input). Is this similar to
> what Pari does? Would it make sense to parallelize ECM/QS by default
> on a multi-core system?
>
> - Robert
>
Bill Hart <goodwillhart@googlemail.com>
	
	
This proposal is absolutely correct. It is *exactly* what I would do,
with one exception. I would not issue a warning that MPQS is going to
start, unless the factorisation is over say 70 digits (~90s).

Bill.

[wbhart]

comment:4

I've just discussed this with Paul Zimmerman and here is what we should do (eventually):

1. Trial factoring for primes up to ~1000
2. SQUFOF for numbers up to ~32-40 bits (use the fast implementation in FLINT - it's 4x faster than anything else)
3. Pollard Rho if we have an efficient implementation
4. tinyQS in FLINT if the number of digits is small enough, i.e. if that is going to be faster than GMP-ECM (we have to profile this to determine the cutoff)
5. GMP-ECM with bound up to n^(1/3)
6. p-1 and p+1 with large bound (it works rarely, but saves MPQS if it happens to work - the runtime compared to MPQS is tiny)
7. MPQS up to ~90 digits if large prime variant, ~100 digits if double large prime variant or ~130 digits if triple large prime variant QS
8. GNFS
9. You are the NSA, so you know what to do.

[zimmermann6]

comment:5

Steps 2) and 3) of my original proposal might be easily implemented using the "finer ECM interface" proposed in #1421.

[zimmermann6]

comment:8

since no progress was done in 2 years, I close that ticket.