mersenneforum.org msieve for only "easy" factorization
 Register FAQ Search Today's Posts Mark Forums Read

 2021-03-20, 17:27 #1 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22×839 Posts msieve for only "easy" factorization 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?
 2021-03-20, 19:00 #2 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 371310 Posts I know it's not Msieve, but you might be able to something similar with YAFU. Maybe B2 will chime in, if I am in error, but to try, use the following command: Code: ./yafu "factor()" -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: Code:  ./yafu "siqs()" -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: Code: -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") Last fiddled with by EdH on 2021-03-20 at 19:17
 2021-03-20, 19:11 #3 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22·839 Posts 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.
2021-03-20, 19:12   #4
bsquared

"Ben"
Feb 2007

22×859 Posts

Quote:
 Originally Posted by EdH I know it's not Msieve, but you might be able to do all this with YAFU. Maybe B2 will chime in, if I am in error, but to try, use the following command: Code: ./yafu "factor()" -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.

2021-03-20, 19:24   #5
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×839 Posts

Quote:
 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!

Last fiddled with by James Heinrich on 2021-03-20 at 19:25

 2021-03-22, 05:55 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 25×5×59 Posts 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) Last fiddled with by LaurV on 2021-03-22 at 05:56

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 22 2020-09-20 21:00 mickfrancis Factoring 5 2015-02-17 14:27 Ryan Computer Science & Computational Number Theory 23 2012-06-03 20:50 Unregistered Homework Help 28 2009-12-14 15:29 Fusion_power Math 13 2004-12-28 20:46

All times are UTC. The time now is 00:30.

Fri May 7 00:30:45 UTC 2021 up 28 days, 19:11, 0 users, load averages: 1.35, 1.56, 1.53