Software to factor arbitrary ~410-bit number

[James Heinrich]

I need to obtain the prime factorization of a number such as this

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

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.

[lukerichards]

Hi James,

You might find this thread useful:

https://mersenneforum.org/showthread.php?t=23078

[James Heinrich]

Useful, yes, but I need more hand-holding than that.

I've gotten as far as something like

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?

[masser]

Would this help?

https://members.loria.fr/PZimmermann...cm/params.html

[James Heinrich]

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.

[VBCurtis]

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.

[James Heinrich]

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.

[VBCurtis]

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:

80372772078870023311028629526527251806209541
79001680667399413021755551127728881024073264821649477463074552981

50 minutes wall-clock time on 8 hyperthreads.

[James Heinrich]

Wow, amazing, thank you. Sure wish I had that compiled for Windows :)

[axn]

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.

[James Heinrich]

Originally Posted by axn

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.

yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12

Thanks axn!