mersenneforum.org Software to factor arbitrary ~410-bit number
 Register FAQ Search Today's Posts Mark Forums Read

 2019-05-15, 21:29 #1 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22·13·73 Posts Software to factor arbitrary ~410-bit number I need to obtain the prime factorization of a number such as this Code: 5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836 Normally I use Dario's excellent ECM page for such tasks and it invariably spits out the factorization I need anywhere from instantly to a few minutes. Except for this number, which seems a hard nut to crack. I've let it run for about 24h running what appears to be about 5000 ECM and still no joy. Well, actually once the trivial factors are removed it's stuck on splitting Code: 6349584074128565251579621474009238287623563015787101780061041692025765962232486337920863526534965038592191721 I was wondering if there is some offline software I might try for such a task, ideally something that I can throw more than one CPU (or GPU for that matter) core at? I did try PARI/GP using factor(
 2019-05-15, 21:35 #2 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25×32 Posts Hi James, You might find this thread useful: https://mersenneforum.org/showthread.php?t=23078
 2019-05-15, 22:01 #3 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22·13·73 Posts Useful, yes, but I need more hand-holding than that. I've gotten as far as something like Code: ecm -inp worktodo.txt -one -c 1000 100000 ... Run 1000 out of 1000: Using B1=100000, B2=40868532, polynomial x^2, sigma=1:187039342 Step 1 took 109ms Step 2 took 94ms But I don't understand (nor particularly want to) how to pick bounds. Is there some kind of parameter I can set to tell it to just auto-choose B1/B2 and increment them as necessary once an appropriate number of curves have been run? I'm kind of looking for a set-and-forget tool where I can just throw a big number at it and (eventually) get my answer back. It also seems to only use one core, unless there's something I missed to specify number of threads?
 2019-05-15, 22:11 #4 masser     Jul 2003 Behind BB 17×113 Posts Would this help? https://members.loria.fr/PZimmermann...cm/params.html
 2019-05-15, 23:34 #5 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22·13·73 Posts Thanks, but not for my purposes. I don't want to pick bounds, I want to feed it a number and get an answer, that's all. Sounds like I'll stick with Dario's ECM site since that works exactly as I want, I'll just need to let it run for some hours/days until it comes up with an answer.
2019-05-16, 01:02   #7
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×13×73 Posts

Quote:
 Originally Posted by VBCurtis If you're on linux, CADO will do what you wish without fuss. ... if you don't mind waiting a day or so, I can feed it to my CADO install and have factors for you posted to this thread.
I'm mostly on Windows, although I can play with that on my server (although that's an 8-core Atom, perhaps not ideal for heavy crunching). I also don't speak Linux fluently.
edit: after a quick test it didn't compile nicely for me, apparently I don't have a Python interpreter either installed or configured.

The SIQS running on Dario's site estimates completion in 3.5 days, although if you want to get me a factorization before then I'm grateful (but it's not urgent). The cofactor is 362 bits which is somewhat smaller than 410 but still not that small.

Last fiddled with by James Heinrich on 2019-05-16 at 01:03

 2019-05-16, 01:23 #8 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5,381 Posts NFS factoring difficulty doubles about every 5 digits, so 48 bits smaller is about 8x faster to factor than the original 410-bit number. Here are your factors: Code: 80372772078870023311028629526527251806209541 79001680667399413021755551127728881024073264821649477463074552981 50 minutes wall-clock time on 8 hyperthreads.
 2019-05-16, 01:26 #9 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 22·13·73 Posts Wow, amazing, thank you. Sure wish I had that compiled for Windows :)
 2019-05-16, 02:44 #10 axn     Jun 2003 5,387 Posts 1. Get yafu, GGNFS sievers, gmp-ecm binary 2. "Tune" yafu 3. Call yafu "factor()" It will take care of all the steps.
2019-05-16, 03:09   #11
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

22×13×73 Posts

Quote:
 Originally Posted by axn 1. Get yafu, GGNFS sievers, gmp-ecm binary 2. "Tune" yafu 3. Call yafu "factor()"
yafu... why didn't I yafu... I have it installed already, just forgot about it.
Code:
yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12
Thanks axn!

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Factoring 87 2019-03-28 13:31 Zach010 Software 21 2019-01-11 05:51 literka Miscellaneous Math 73 2013-11-17 10:33 skan Programming 14 2013-03-24 00:32 JuanTutors Math 3 2007-05-16 12:13

All times are UTC. The time now is 07:36.

Mon Aug 15 07:36:04 UTC 2022 up 39 days, 2:23, 1 user, load averages: 1.02, 1.05, 1.15