mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2021-03-20, 17:27   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22×839 Posts
Default 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?
James Heinrich is offline   Reply With Quote
Old 2021-03-20, 19:00   #2
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

371310 Posts
Default

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(<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:
Code:
 ./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:
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
EdH is offline   Reply With Quote
Old 2021-03-20, 19:11   #3
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22·839 Posts
Default

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.
James Heinrich is offline   Reply With Quote
Old 2021-03-20, 19:12   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×859 Posts
Default

Quote:
Originally Posted by EdH View Post
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(<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.
bsquared is offline   Reply With Quote
Old 2021-03-20, 19:24   #5
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22×839 Posts
Default

Quote:
Originally Posted by bsquared View Post
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
James Heinrich is offline   Reply With Quote
Old 2021-03-22, 05:55   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

25×5×59 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"New" same approach that isn't factorization Alberico Lepore Alberico Lepore 22 2020-09-20 21:00
"Quadratic time factorization" patent mickfrancis Factoring 5 2015-02-17 14:27
factorization of "almost" prime numbers Ryan Computer Science & Computational Number Theory 23 2012-06-03 20:50
Many "Zeros" in Public Key, factorization easy ? Unregistered Homework Help 28 2009-12-14 15:29
"Trivial" factorization algorithms 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.