Software to factor arbitrary ~410-bit number
 

I need to obtain the prime factorization of a number such as this[code]5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836[/code]Normally I use Dario's excellent [url=https://www.alpertron.com.ar/ECM.HTM]ECM page[/url] 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[/code]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 [i]factor(<number)[/i] 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.

Hi James,

You might find this thread useful:

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

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

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[/code]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?

Would this help?

[URL="https://members.loria.fr/PZimmermann/records/ecm/params.html"]https://members.loria.fr/PZimmermann/records/ecm/params.html[/URL]

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.

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.

[QUOTE=VBCurtis;516873]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.[/QUOTE]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. :redface:
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.

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[/code]
50 minutes wall-clock time on 8 hyperthreads.

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

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.

[QUOTE=axn;516880]1. Get yafu, GGNFS sievers, gmp-ecm binary
2. "Tune" yafu
3. Call yafu "factor(<your number>)"[/QUOTE]yafu... why didn't I yafu... I have it installed already, just forgot about it.
[code]yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12[/code]
Thanks [i]axn[/i]! :bow:

[QUOTE=VBCurtis;516876]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[/code]
50 minutes wall-clock time on 8 hyperthreads.[/QUOTE]

For fun... 36 minutes by SIQS:

[CODE]starting SIQS on c109: 6349584074128565251579621474009238287623563015787101780061041692025765962232486337920863526534965038592191721

==== sieve params ====
n = 109 digits, 362 bits
factor base: 207584 primes (max prime = 6041731)
single large prime cutoff: 906259650 (150 * pmax)
double large prime range from 46 to 54 bits
double large prime range from 36502513476361 to 13275618366497020
allocating 12 large prime slices of factor base
buckets hold 2048 elements
large prime hashtables have 2359296 bytes
using AVX512 enabled 32k sieve core
sieve interval: 12 blocks of size 32768
polynomial A has ~ 14 factors
using multiplier of 1
using SPV correction of 20 bits, starting at offset 29
trial factoring cutoff at 109 bits

==== sieving in progress (256 threads): 207648 relations needed ====
==== Press ctrl-c to abort and save state ====
213768 rels found: 51473 full + 162295 from 3078485 partial, (1537.69 rels/sec)

sieving required 22440891 total polynomials (5773 'A' polynomials)
trial division touched 816476743 sieve locations out of 17648234790912
squfof: 0 failures, 2482767 attempts, 457120483 outside range, 12555665 prp, 2321648 useful
total reports = 816476743, total surviving reports = 472967225
total blocks sieved = 538587336,avg surviving reports per block = 0.88
QS elapsed time = 2035.4923 seconds.
...
lanczos halted after 3118 iterations (dim = 197110)
recovered 14 nontrivial dependencies
Lanczos elapsed time = 93.3500 seconds.
Sqrt elapsed time = 0.7600 seconds.
SIQS elapsed time = 2131.4362 seconds.


***factors found***

P44 = 80372772078870023311028629526527251806209541
P65 = 79001680667399413021755551127728881024073264821649477463074552981


[/CODE]

[QUOTE=bsquared;516908]For fun... 36 minutes by SIQS:[/QUOTE]
256 threads? :shock: What processor is that?

[QUOTE=axn;516909]256 threads? :shock: What processor is that?[/QUOTE]

[QUOTE=yafu v1.35-beta]
detected Intel(R) Xeon Phi(TM) CPU 7210 @ 1.30GHz
detected L1 = 32768 bytes, L2 = 1048576 bytes, CL = 64 bytes
measured cpu frequency ~= 1297.000770
[/QUOTE]

64 cores, 4 hyperthreads per core; it acts like a sieve-friendly GPU.

[QUOTE=James Heinrich;516882]yafu... why didn't I yafu... I have it installed already, just forgot about it.[/QUOTE]So I let it run for an hour or two overnight and it did exactly what I wanted:[code]yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12

P1 = 2
P1 = 2
P2 = 17
P2 = 43
P4 = 1907
P9 = 148922387
P44 = 80372772078870023311028629526527251806209541
P65 = 79001680667399413021755551127728881024073264821649477463074552981[/code]albeit extremely verbosely with tens (hundreds?) of thousands of lines of stuff like:[code]2484 124809929372509 224852862953705734163711291
2736 81689936843131 219486238756129466725063989
2736 148682315369983 219486238756588041585847851
2484 162497197129847 224852862957929937234699210
2484 258181694630701 224852862955171329218701786
2484 79893963420767 224852862959184885179883596
2736 52015090684045 219486238755244569165277559
2484 95260187304253 224852862957853214745664415
2484 123822558294469 224852862954159224783743291
2736 77036731878323 219486238752425401447998675
2484 104582954047259 224852862955390973830660807
2736 99968994776407 219486238757645654923105819
2736 236049971433649 219486238752721810750461124
2736 96202602994523 219486238754915888222368567
2736 111855459347017 219486238756502505324264408
2736 236049971433649 219486238752721810750461124
2736 174430633987859 219486238750088021464795804
2484 80433616080781 224852862959206056424178599
2484 112743893490227 224852862959183716661681013
2484 95887700959069 224852862955704924321522300
2736 203203689199651 219486238764784090149645668
2484 104197709439407 224852862957113690143384847
2736 103246625437715 219486238759337210812421743
2484 216599904445571 224852862956048355481589736
2484 85357935594391 224852862956095450796170855
2736 68407037230045 219486238752340869238887827
2736 162996849442985 219486238757483785913262416
2484 85967592141049 224852862956184628184011883
2736 411261153225155 219486238758742013983637186
2736 231679070567137 219486238755140736617124507
2736 2760880173455 219486238755276485706764776[/code]I couldn't find a "quiet" switch to make it less verbose.

[QUOTE=James Heinrich;516913]So I let it run for an hour or two overnight and it did exactly what I wanted:[code]yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12

P1 = 2
P1 = 2
P2 = 17
P2 = 43
P4 = 1907
P9 = 148922387
P44 = 80372772078870023311028629526527251806209541
P65 = 79001680667399413021755551127728881024073264821649477463074552981[/code]albeit extremely verbosely with tens (hundreds?) of thousands of lines of stuff like:[code]2484 124809929372509 224852862953705734163711291
2736 81689936843131 219486238756129466725063989
2736 148682315369983 219486238756588041585847851
2484 162497197129847 224852862957929937234699210
2484 258181694630701 224852862955171329218701786
2484 79893963420767 224852862959184885179883596
2736 52015090684045 219486238755244569165277559
2484 95260187304253 224852862957853214745664415
2484 123822558294469 224852862954159224783743291
2736 77036731878323 219486238752425401447998675
2484 104582954047259 224852862955390973830660807
2736 99968994776407 219486238757645654923105819
2736 236049971433649 219486238752721810750461124
2736 96202602994523 219486238754915888222368567
2736 111855459347017 219486238756502505324264408
2736 236049971433649 219486238752721810750461124
2736 174430633987859 219486238750088021464795804
2484 80433616080781 224852862959206056424178599
2484 112743893490227 224852862959183716661681013
2484 95887700959069 224852862955704924321522300
2736 203203689199651 219486238764784090149645668
2484 104197709439407 224852862957113690143384847
2736 103246625437715 219486238759337210812421743
2484 216599904445571 224852862956048355481589736
2484 85357935594391 224852862956095450796170855
2736 68407037230045 219486238752340869238887827
2736 162996849442985 219486238757483785913262416
2484 85967592141049 224852862956184628184011883
2736 411261153225155 219486238758742013983637186
2736 231679070567137 219486238755140736617124507
2736 2760880173455 219486238755276485706764776[/code]I couldn't find a "quiet" switch to make it less verbose.[/QUOTE]Redirect STDIN and STDERR to /dev/null

[QUOTE=xilman;516916]Redirect STDIN and STDERR to /dev/null[/QUOTE]I didn't even know that STDERR was a thing [b]in Windows[/b], [url=https://support.microsoft.com/en-ca/help/110930/redirecting-error-messages-from-command-prompt-stderr-stdout]but it is[/url], and that helps, thanks.[code]yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12 2> nul[/code]

[QUOTE=xilman;516916]Redirect STDIN [snip] to /dev/null[/QUOTE]STD[b]IN[/b]?

Two men are having a conversation, but both are only listening. :razz:

[QUOTE=James Heinrich;516918]I didn't even know that STDERR was a thing [B]in Windows[/B], [URL="https://support.microsoft.com/en-ca/help/110930/redirecting-error-messages-from-command-prompt-stderr-stdout"]but it is[/URL], and that helps, thanks.[code]yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12 2> nul[/code][/QUOTE]Hasn't it been a thing on MS operating systems since c compilers on MSDOS?
STDERR redirects differently than STDOUT. If a programmer is not careful, a STDOUT portion of an error message gets redirected and the STDERR portion still goes to the cmd console, unless the user takes rare care.

[url]https://stackoverflow.com/questions/482678/how-to-capture-stderr-on-windows-dos[/url]

[QUOTE=retina;516920]STD[b]IN[/b]?

Two men are having a conversation, but both are only listening. :razz:[/QUOTE]UBD

[QUOTE=kriesel;516921]Hasn't it been a thing on MS operating systems since c compilers on MSDOS?[/QUOTE]
It has, but we all have our strengths and weaknesses, and not all people are "old dinosaurs" like us. Some barely remember WinXP or '98, and only heard "DOS" in the "DoS" context (Denial of Service).

CP/M wants to play too.

[QUOTE=Uncwilly;516975]CP/M wants to play too.[/QUOTE]An I/O pack, based on a couple of ideas by DEC called RT-11 and OS/8

I've used all three.

[QUOTE=xilman;516979]An I/O pack, based on a couple of ideas by DEC called RT-11 and OS/8

I've used all three.[/QUOTE]When I were a bit younger computers were humans. A computer was a profession, not a machine. And you powered them with booze and candy. You programmed them with standard natural language instructions. And they made lots of [strike]mis-steaks[/strike] mistakes.

Geez, you young folks here just don't know how good you have it all.

[size=1]Get off my lawn you rotten little whipper-snappers.[/size]

[QUOTE=retina;516980]When I were a bit younger computers were humans. A computer was a profession, not a machine. And you powered them with booze and candy. You programmed them with standard natural language instructions. And they made lots of [strike]mis-steaks[/strike] mistakes.

Geez, you young folks here just don't know how good you have it all.

[size=1]Get off my lawn you rotten little whipper-snappers.[/size][/QUOTE]Been there, done that. :paul:

Yeah, we used CP/M and RSx-11m too, we even believed (at that time, under the communist guvernment) that they were Romanian inventions :smile: