mersenneforum.org Independent factorization of large numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2022-01-19, 07:08 #1 Lessiv   Jan 2022 19 Posts Independent factorization of large numbers Dear math gurus, Please tell me why most number factorization programs do not use a GPU? I need to factorize not a small number (154 characters), tell me is it really possible to do this on a home computer? I'm going to use JAFU or MSiev, I realized from the forum that it is required to use the GNFS algorithm, please tell me - am I in the right direction? Last fiddled with by Lessiv on 2022-01-19 at 08:04
2022-01-19, 10:30   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

1129510 Posts

Quote:
 Originally Posted by Lessiv Dear math gurus, Please tell me why most number factorization programs do not use a GPU? I need to factorize not a small number (154 characters), tell me is it really possible to do this on a home computer? I'm going to use JAFU or MSiev, I realized from the forum that it is required to use the GNFS algorithm, please tell me - am I in the right direction?
154 decimal digits sounds suspiciously like a 512-bit RSA key to me, though such values are actually 157 digits long.

As a matter of interest, what is your number? Post it here and several people will be able to factor it for you within a day or few.

Most GPUs do not have enough memory to be effective with the GNFS.

2022-01-19, 10:47   #3
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

33·239 Posts

Quote:
 Originally Posted by xilman 154 decimal digits sounds suspiciously like a 512-bit RSA key to me, though such values are actually 157 digits long.
Erm?

My calculator says that 154รlogโ10 = 511.5769... so 154 seems right.
Quote:
 Originally Posted by xilman Post it here and several people will be able to factor it for you within a day or few.
Haha, maybe.

Ability to do so doesn't guarantee an equivalent amount of desire or motivation to do so. I wonder if the OP is willing to offer something in return?

2022-01-19, 11:24   #4
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2C1F16 Posts

Quote:
 Originally Posted by retina Erm? My calculator says that 154รlogโ10 = 511.5769... so 154 seems right.Haha, maybe. Ability to do so doesn't guarantee an equivalent amount of desire or motivation to do so. I wonder if the OP is willing to offer something in return?
You are correct. Mea culpa.

2022-01-19, 11:26   #5
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2C1F16 Posts

Quote:
 Originally Posted by retina Ability to do so doesn't guarantee an equivalent amount of desire or motivation to do so. I wonder if the OP is willing to offer something in return?
If the reason why it is to be factored --- for instance, for which specific key it is the public modulus --- were offered I may be motivated to perform the factorization.

2022-01-19, 11:29   #6
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

25·11·17 Posts

Quote:
 Originally Posted by xilman Post it here and several people will be able to factor it for you within a day or few.

If it is an 512 bit RSA number people may be reluctant to factor it without proof of its source. I believe a decent modern pc(or an AWS instance) can factor this in 2 or 3 weeks.

 2022-01-19, 16:22 #7 Lessiv   Jan 2022 19 Posts Yes, you're right - it's a RSA modulud (N) There was a "Factoring as a Service" project on GIT, I wanted to use just such a service for factoring numbers, but the project is no longer active, looking for a solution - I found this forum. Regarding the legality, there are no violations, keys of this length are no longer used, as evidenced by the service itself that was used by AMAZON (AWS). For the assistance provided, I am ready to thank the helper. Last fiddled with by Lessiv on 2022-01-19 at 16:23
 2022-01-19, 16:37 #8 chris2be8     Sep 2009 13·179 Posts There are several programs you could use to factor it: ggnfs - this works better if you also have msieve. Search for factMsieve.pl or factmsieve.py for scripts to drive it. yafu - this will need the lattice siever from ggnfs and msieve. cado-nfs - this is a complete package that does not need other software. Whatever you use I suggest you start by factoring a 100 digit number as a quick test. Then work up by factoring a 110 digit number, then a 120 digit number, etc until you get up to 140 or 150 digits before tackling your 154 digit number. Since you know it's a RSA key there is no need to run ECM before you start GNFS. ECM is only useful for numbers that might have a small factor.
2022-01-19, 16:57   #9
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

32×5×251 Posts

Quote:
 Originally Posted by Lessiv Yes, you're right - it's a RSA modulud (N) There was a "Factoring as a Service" project on GIT, I wanted to use just such a service for factoring numbers, but the project is no longer active, looking for a solution - I found this forum. Regarding the legality, there are no violations, keys of this length are no longer used, as evidenced by the service itself that was used by AMAZON (AWS). For the assistance provided, I am ready to thank the helper.
Keys of this length should not be used. However, they are.

So which key is it? If there are no violations I can't see that you have any real reason to hide its identity.

2022-01-19, 16:59   #10
Lessiv

Jan 2022

1910 Posts

Thanks for the detailed answer, that's exactly what I assumed (according to ECM).
I have a PC with an Intel I9 processor, will use it.
Assumed that there is a person or a company on the forum that has a more solid computer package, I thought to use the help, but apparently I'll have to try it myself by trial and error :ัะปัะฑะบะฐ:

Or maybe someone understands how to rent AWS on Amazon, for faster factoring?
According to the description, this number was factorized in less than 24 hours, and this is about 6 years ago

Quote:
 Originally Posted by chris2be8 Whatever you use I suggest you start by factoring a 100 digit number as a quick test. Then work up by factoring a 110 digit number, then a 120 digit number, etc until you get up to 140 or 150 digits before tackling your 154
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.

Last fiddled with by Lessiv on 2022-01-19 at 17:06

2022-01-19, 17:02   #11
Lessiv

Jan 2022

19 Posts

Quote:
 Originally Posted by xilman Keys of this length should not be used. However, they are. So which key is it? If there are no violations I can't see that you have any real reason to hide its identity.
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

 Similar Threads Thread Thread Starter Forum Replies Last Post jpcu1237 Tales From the Crypt(o) 18 2020-07-16 22:23 CRGreathouse Factoring 55 2014-04-11 15:05 HellGauss Math 5 2012-04-12 14:01 ET_ Factoring 15 2008-03-12 21:24 Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 04:01.

Sat May 21 04:01:43 UTC 2022 up 37 days, 2:03, 0 users, load averages: 2.04, 2.01, 1.71