20210320, 17:27  #1 
"James Heinrich"
May 2004
exNorthern Ontario
2^{2}·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 postECM composite is <= 80 (configurable) digits, and also avoid wasting time doing a partialthenabort 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? 
20210320, 19:00  #2 
"Ed Hall"
Dec 2009
Adirondack Mtns
3713_{10} Posts 
I know it's not Msieve, but you might be able to something similar with YAFU. Maybe B^{2} will chime in, if I am in error, but to try, use the following command:
Code:
./yafu "factor(<candidate>)" siqsT 30 one 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(<candidate>)" siqsT 30 one 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 tlevel of "num") Last fiddled with by EdH on 20210320 at 19:17 
20210320, 19:11  #3 
"James Heinrich"
May 2004
exNorthern Ontario
110100011100_{2} 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.

20210320, 19:12  #4  
"Ben"
Feb 2007
3433_{10} Posts 
Quote:
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 postecm 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. 

20210320, 19:24  #5  
"James Heinrich"
May 2004
exNorthern Ontario
2^{2}×839 Posts 
Quote:
That actually looks pretty close to what I'm looking for. Thanks Ben! Last fiddled with by James Heinrich on 20210320 at 19:25 

20210322, 05:55  #6 
Romulan Interpreter
Jun 2011
Thailand
22340_{8} 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 oneliner 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 20210322 at 05:56 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
"New" same approach that isn't factorization  Alberico Lepore  Alberico Lepore  22  20200920 21:00 
"Quadratic time factorization" patent  mickfrancis  Factoring  5  20150217 14:27 
factorization of "almost" prime numbers  Ryan  Computer Science & Computational Number Theory  23  20120603 20:50 
Many "Zeros" in Public Key, factorization easy ?  Unregistered  Homework Help  28  20091214 15:29 
"Trivial" factorization algorithms  Fusion_power  Math  13  20041228 20:46 