Independent factorization of large numbers - Page 2

VBCurtis · 2022-01-19, 17:03

If you can run linux, use cado-nfs. Everything is automated, you simply invoke "cado-nfs.py {input number}" and wait / watch. The job will run faster if you first fetch the updated parameters files from the Cado-nfs forum here. I recommend 16GB ram if you use CADO for your desired factorization; 8GB might work, but might not be enough.

If all you have is windows, YAFU is the way to go- it controls msieve and ggnfs to manage the entire job too.

Whatever you use, run a small job like 100-110 digits first, to learn what is supposed to happen. It'll take maybe an hour, depending on how fast your machine is. Time to factor doubles every 5-5.5 digits, so a C154 will take about 4x as long as a C143; around 70 times longer than a C120. I'd run a second job in the 120-130 digit range before I tried C150+.

henryzz · 2022-01-19, 17:36

If you have windows it is possible to get CADO working on WSL2 although this requires fixing a few broken links.

Stargate38 · 2022-01-19, 17:55

Once you factor the number, could you please publish the factors? I'm curious as to which number it is.

xilman · 2022-01-19, 18:21

Quote:

Originally Posted by Lessiv

I do not hide my identity, it's like a race - a game, who will understand one software mechanism faster.
It is just necessary that this number is NOT in the public domain, so that other participants do not use it

Fair enough. In that case I will not offer to factor it for you. It would not be fair on the other competitors.

Good luck!

firejuggler · 2022-01-19, 18:39

And are you sure it is a product of only 2 factors? cause you know.. if it is not it can ( low prob) be factored by ECM.

LaurV · 2022-01-20, 11:51

Quote:

Originally Posted by Lessiv

Sorry, but here I do not understand - why should I waste precious time. Of course, I will run a small number, just to check that everything is set up as it should and then skip the factoring of the Real number.

To get the feeling of how it goes, and to learn something in the process. And to gain the patience... For example my computer(s), anything between 6 cores and 18 cores, can factor a 100 digits number in minutes, but the time doubles with every 4-5-6 digits, depending on the number and on the system. So, a 154 digits can take anything between few days and few weeks.

bur · 2022-01-20, 15:12

If you use yafu, make sure it will not attempt ECM! As already mentioned it's useless for your number since there will be no small factors. You can do that by invoking yafu factor(12345) -noecm -threads n where n is the number of threads.

Stargate38 · 2022-01-20, 17:06

You can also do "yafu nfs(number) -threads n".

retina · 2022-01-20, 17:41

The suggestion to practice on smaller numbers first is very good. No sense in wasting weeks on a large number only to discover your configuration is wrong and it fails.

Here are some numbers you can use to practice:
https://en.wikipedia.org/wiki/RSA_numbers

Lessiv · 2022-01-21, 16:12

I ran msieve and ggnfs and looked for 100 digit number
My computer (i9) found it in 12 minutes.
I have a question: how to run along with the processor and CUDA?
I think it will be even faster.

VBCurtis · 2022-01-21, 16:40

Only the first step (polynomial selection) is cuda-enabled.
If you use a version of msieve compiled for CUDA, it will automatically use the GPU for that step.

2022-01-20, 17:06	#19
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 2BD₁₆ Posts	You can also do "yafu nfs(number) -threads n". Last fiddled with by Stargate38 on 2022-01-20 at 17:06 Reason: forgot period

2022-01-21, 16:12	#21
Lessiv Jan 2022 19 Posts	I ran msieve and ggnfs and looked for 100 digit number My computer (i9) found it in 12 minutes. I have a question: how to run along with the processor and CUDA? I think it will be even faster. Last fiddled with by Lessiv on 2022-01-21 at 16:13

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Breakthrough in Very Large Integer factorization?	jpcu1237	Tales From the Crypt(o)	18	2020-07-16 22:23
Methods of attacking a large factorization	CRGreathouse	Factoring	55	2014-04-11 15:05
An equivalent problem for factorization of large numbers	HellGauss	Math	5	2012-04-12 14:01
Fermat numbers factorization	ET_	Factoring	15	2008-03-12 21:24
How do I get LARGE numbers	Bundu	Software	5	2004-08-26 01:56

2022-01-19, 17:03	#12
VBCurtis "Curtis" Feb 2005 Riverside, CA 5276₁₀ Posts	If you can run linux, use cado-nfs. Everything is automated, you simply invoke "cado-nfs.py {input number}" and wait / watch. The job will run faster if you first fetch the updated parameters files from the Cado-nfs forum here. I recommend 16GB ram if you use CADO for your desired factorization; 8GB might work, but might not be enough. If all you have is windows, YAFU is the way to go- it controls msieve and ggnfs to manage the entire job too. Whatever you use, run a small job like 100-110 digits first, to learn what is supposed to happen. It'll take maybe an hour, depending on how fast your machine is. Time to factor doubles every 5-5.5 digits, so a C154 will take about 4x as long as a C143; around 70 times longer than a C120. I'd run a second job in the 120-130 digit range before I tried C150+.

2022-01-19, 17:36	#13
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 13540₈ Posts	If you have windows it is possible to get CADO working on WSL2 although this requires fixing a few broken links.

2022-01-19, 17:55	#14
Stargate38 "Daniel Jackson" May 2011 14285714285714285714 1275₈ Posts	Once you factor the number, could you please publish the factors? I'm curious as to which number it is.

2022-01-19, 18:39	#16
firejuggler "Vincent" Apr 2010 Over the rainbow 2·3·11·43 Posts	And are you sure it is a product of only 2 factors? cause you know.. if it is not it can ( low prob) be factored by ECM.

2022-01-20, 15:12	#18
bur Aug 2020 796581e-4;32539e-3 503 Posts	If you use yafu, make sure it will not attempt ECM! As already mentioned it's useless for your number since there will be no small factors. You can do that by invoking yafu factor(12345) -noecm -threads n where n is the number of threads.

2022-01-20, 17:41	#20
retina Undefined "The unspeakable one" Jun 2006 My evil lair 3·19·113 Posts	The suggestion to practice on smaller numbers first is very good. No sense in wasting weeks on a large number only to discover your configuration is wrong and it fails. Here are some numbers you can use to practice: https://en.wikipedia.org/wiki/RSA_numbers

2022-01-21, 16:40	#22
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²×1,319 Posts	Only the first step (polynomial selection) is cuda-enabled. If you use a version of msieve compiled for CUDA, it will automatically use the GPU for that step.