msieve for only "easy" factorization

[James Heinrich]

I would like to use msieve to work through a large list of numbers (anywhere from c60 to c200 or thereabout) and pick off the "easy" factorizations (that take a couple minutes or less). Specifically I would like to do the appropriate ECM, and possibly some QS if it doesn't take very long. Right now I'm making do with the -d "deadline" parameter to abort after 2 minutes, but this isn't very efficient -- sometimes 2.1 minutes would've got me a complete factorization, and sometimes 2 minutes doesn't even finish ECM. What I would like to see is a flag to enabled me to specify "do ECM, and QS on numbers up to <80> digits, if bigger than that then abort". That would let me always get complete factorization if the post-ECM composite is <= 80 (configurable) digits, and also avoid wasting time doing a partial-then-abort QS when it'll never finish.

Is there such a parameter that I've been missing? If not, any chance such functionality could be added?

[EdH]

I know it's not Msieve, but you might be able to something similar with YAFU. Maybe B² will chime in, if I am in error, but to try, use the following command:

./yafu "factor(<candidate>)" -siqsT 30 -one

You would need to first compile a YAFU binary without the NFS=1 switch and then YAFU should call the appropriate amount of ECM and then automatically switch to SIQS until the "-siqsT #" tells it to give up. The -one appears to be necessary to keep YAFU from looping the SIQS operation.

I have tested this on a single basis, but the commands should be able to be sent via a script or by using the YAFU "-batchfile" option.

Edit: In thinking a little further, YAFU's ECM will be based on the candidate size. If you choose to limit it via your ECM use, you could use the following for the YAFU call, after the ECM call:

 ./yafu "siqs(<candidate>)" -siqsT 30 -one

Edit 2: I believe you can tell YAFU what level to perform ECM to, but I would need to read the docs further to post that and I have already submitted this. . . (maybe more later. . .)

Edit 3 (later): -pretest [num] can be used to limit the ECM. From the docs:

-pretest [num]    Use this switch with factor() for ECM pretesting of the input number. 
                Optionally provide an integer value specifing the maximum level of 
                pretesting to do (up to "num" digits, or a t-level of "num")

[James Heinrich]

Thanks for the suggestion. Not quite what I'm looking for, it's roughly equivalent to what I have now with msieve -d 1 -- the time is still spent in QS even if it's obvious to the observer it'll never finish within the specified time.

[bsquared]

Originally Posted by EdH

I know it's not Msieve, but you might be able to do all this with YAFU. Maybe B² will chime in, if I am in error, but to try, use the following command:

./yafu "factor(<candidate>)" -siqsT 30 -one

You would need to first compile a YAFU binary without the NFS=1 switch and then YAFU should call the appropriate amount of ECM and then automatically switch to SIQS until the "-siqsT #" tells it to give up. The -one appears to be necessary to keep YAFU from looping the SIQS operation.

I have tested this on a single basis, but the commands should be able to be sent via a script or by using the YAFU "-batchfile" option.

To avoid NFS, rather than recompiling, I think you can just use -xover 200 or something (which sets the crossover from QS to NFS at 200 digits; i.e., never).

There is nothing in yafu (or msieve, that I'm aware of, but maybe Jasonp will chime in if I'm wrong) that will tell it to give up if a post-ecm number is larger than some configurable bound.

If you just want to get the ecm out of the way on a list of number, yafu's -pretest option might be something to look at, although you probably are already aware of that.

[James Heinrich]

Originally Posted by bsquared

If you just want to get the ecm out of the way on a list of number, yafu's -pretest option might be something to look at, although you probably are already aware of that.

Make no such assumptions about me. I've only been here 17 years, I don't actually know what I'm doing.

That actually looks pretty close to what I'm looking for. Thanks Ben!

[LaurV]

Can you sort your list by size? (i.e. is that something static or it is dynamically generated, one side the numbers are added, the other side they are factored?). Are the numbers in the list separated by (what? CRLF? comma? space?). Can you extract the shorter lines (less than 80 digits, etc, just one-liner in perl, or pari, or whatever) and pass only those to yafu with the snfs switch on, while pass the other with ecm or pretest only? What are those numbers? (if not big deal/secret)