mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2019-05-15, 21:29   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22·13·73 Posts
Default 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(<number) but that's only using one core, and sadly gives no progress output until it comes up with the final answer. Maybe I'm using it wrong. Other suggestions very much welcome.
James Heinrich is offline   Reply With Quote
Old 2019-05-15, 21:35   #2
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Hi James,

You might find this thread useful:

https://mersenneforum.org/showthread.php?t=23078
lukerichards is offline   Reply With Quote
Old 2019-05-15, 22:01   #3
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22·13·73 Posts
Default

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?
James Heinrich is offline   Reply With Quote
Old 2019-05-15, 22:11   #4
masser
 
masser's Avatar
 
Jul 2003
Behind BB

17×113 Posts
Default

Would this help?

https://members.loria.fr/PZimmermann...cm/params.html
masser is offline   Reply With Quote
Old 2019-05-15, 23:34   #5
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22·13·73 Posts
Default

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.
James Heinrich is offline   Reply With Quote
Old 2019-05-16, 00:28   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

150516 Posts
Default

If you're on linux, CADO will do what you wish without fuss. Google CADO-NFS and follow the git download instructions from the official page.

command line would be ./cado-nfs.py {input number}

If you want to use less than the full number of hyperthreads available on your machine, append the flag --server-threads=4 (change 4 to number of hyperthreads you wish to use).

Or, 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.

EDIT: I just noticed the cofactor is much smaller than 410 bits; I'll have factors posted here in about an hour.

Last fiddled with by VBCurtis on 2019-05-16 at 00:31
VBCurtis is offline   Reply With Quote
Old 2019-05-16, 01:02   #7
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22×13×73 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
James Heinrich is offline   Reply With Quote
Old 2019-05-16, 01:23   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5,381 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2019-05-16, 01:26   #9
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22·13·73 Posts
Default

Wow, amazing, thank you. Sure wish I had that compiled for Windows :)
James Heinrich is offline   Reply With Quote
Old 2019-05-16, 02:44   #10
axn
 
axn's Avatar
 
Jun 2003

5,387 Posts
Default

1. Get yafu, GGNFS sievers, gmp-ecm binary
2. "Tune" yafu
3. Call yafu "factor(<your number>)"

It will take care of all the steps.
axn is online now   Reply With Quote
Old 2019-05-16, 03:09   #11
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

22×13×73 Posts
Default

Quote:
Originally Posted by axn View Post
1. Get yafu, GGNFS sievers, gmp-ecm binary
2. "Tune" yafu
3. Call yafu "factor(<your number>)"
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!
James Heinrich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor-finding algorithms (and software) lukerichards Factoring 87 2019-03-28 13:31
Prime number software. Zach010 Software 21 2019-01-11 05:51
Number 59649589127497217 is a factor of Fermat number F7 literka Miscellaneous Math 73 2013-11-17 10:33
software advise? big number with GUI skan Programming 14 2013-03-24 00:32
Time to test arbitrary number 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔