mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Independent factorization of large numbers (https://www.mersenneforum.org/showthread.php?t=27511)

 Lessiv 2022-01-19 07:08

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?

 xilman 2022-01-19 10:30

[QUOTE=Lessiv;598309]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?[/QUOTE]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.

 retina 2022-01-19 10:47

[QUOTE=xilman;598314]154 decimal digits sounds suspiciously like a 512-bit RSA key to me, though such values are actually 157 digits long.[/QUOTE]Erm?

My calculator says that 154×log₂10 = 511.5769... so 154 seems right.[QUOTE=xilman;598314]Post it here and several people will be able to factor it for you within a day or few.[/QUOTE]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?

 xilman 2022-01-19 11:24

[QUOTE=retina;598317]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?[/QUOTE]You are correct. Mea culpa.

 xilman 2022-01-19 11:26

[QUOTE=retina;598317]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?[/QUOTE]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.

 henryzz 2022-01-19 11:29

[QUOTE=xilman;598314]Post it here and several people will be able to factor it for you within a day or few.
[/QUOTE]

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.

 Lessiv 2022-01-19 16:22

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.

 chris2be8 2022-01-19 16:37

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.

 xilman 2022-01-19 16:57

[QUOTE=Lessiv;598332]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.[/QUOTE]Keys of this length [I]should[/I] 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.

 Lessiv 2022-01-19 16:59

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=chris2be8;598334]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[/QUOTE]
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.

 Lessiv 2022-01-19 17:02

[QUOTE=xilman;598336]Keys of this length [I]should[/I] 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.[/QUOTE]

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

All times are UTC. The time now is 23:06.