Didn't even find a useless factor of an uninteresting number! Take that! - Page 26

storflyt32 · 2016-11-16, 08:59

Can you really have the factors of RSA-1024 without having to factorize it?

We all know that it should not be possible.

http://factordb.com/index.php?id=1100000000882813413

Notice that this is another number than the mentioned RSA-1024.

But this number will probably not be factorized either.

But I could possibly do so if I will, because here I ended up with the individual factors.

Still working on this, of course.

Thanks for the suggestion, by the way.

https://en.wikipedia.org/wiki/Coppersmith_method

https://en.wikipedia.org/wiki/Coppersmith%27s_attack

I am able to find two selected links for the given suggestion.

Any better suggestions for the correct one would be welcome.

CRGreathouse · 2016-11-16, 18:50

Quote:

Originally Posted by storflyt32

https://en.wikipedia.org/wiki/Coppersmith_method

https://en.wikipedia.org/wiki/Coppersmith%27s_attack

I am able to find two selected links for the given suggestion.

Any better suggestions for the correct one would be welcome.

This one has a worked example, which you could mimic if you knew enough final digits of one of the factors:
http://pari.math.u-bordeaux.fr/docht...#zncoppersmith

Quote:

Originally Posted by storflyt32

Can you really have the factors of RSA-1024 without having to factorize it?

We all know that it should not be possible.

Is anyone suggesting otherwise?

I mean, it's possible -- perhaps RSA Security, contrary to their claims, kept the original prime factors that they chose. But I don't see the relevance in any case.

storflyt32 · 2016-11-18, 04:50

Thanks for the link.

http://factordb.com/index.php?id=1100000000193628325

Not prime (when using isprime in Yafu).

storflyt32 · 2016-11-21, 12:15

http://factordb.com/index.php?id=1100000000883308511

Not for free. Took quite a while to do this one.

Became a PRP120 first, next a P120 in the final output.

Total factoring time = 81701.2252 seconds

storflyt32 · 2016-11-25, 22:17

http://factordb.com/index.php?id=1100000000884781588

One less to go.

Digging a little deeper here, this took quite a while to get at.

storflyt32 · 2016-12-04, 17:47

http://factordb.com/index.php?id=1100000000885545955

http://factordb.com/index.php?id=1100000000885687682

http://factordb.com/index.php?id=1100000000885687293

Should tell that I was unfortunate to have it blow this time when pressing ^C and next having the window close in front of me.

I did in fact have both the smaller factors here, even though the second one took quite some time to get at.

But perhaps you already guessed the answer here.

Not that small in fact when it comes to the first of the links, because even though the server, or maybe someone else in between did this one, I was able to factor it using the brute method, but next letting it run once again, this time by means of ecm.

Using ecm with 2^21 curves did not work out, so I tried using 2^22 curves instead.

The factors were found after 858340 of 4194304 curves, making this a quite heavy one.

Next I did not report it, but it did take quite a long time.

Once again we are apparently back at an incomplete result where the number in question most likely is not able to become factored.

I leave it for someone else to decide whether or not this should be updated, but at least you should now be able to know the factors.

Edit: Could give it yet another try, but it could take a day or more before getting the result.

storflyt32 · 2016-12-12, 03:43

Did not extend or include the last one down to the smaller factors.

http://factordb.com/index.php?id=1100000000411903471

But I happened to read around here during the past weekend and noticed the P83 in this number.

When such a thing happens, a little more should be attempted.

With a disc borking as well, this became slightly difficult, but apparently adding both the P29 and P30 here.

Also adding the P41 and next the P86, making for a complete factorization.

But also should be noted by possibly knowing the two P90 factors of a C180 does not necessarily return a desired result when it comes to the rest, so when this is the case, I rather prefer to make a note of it when the remaining factors are of some size.

As an example, take the product of the P83 and P86 and give the rest a try.

http://factordb.com/index.php?id=1100000000886975937

I could leave it running overnight and have a look at it tomorrow.

storflyt32 · 2016-12-12, 15:15

Returning back to the computer, the second link had run out and another number being computed had found a quite larger factor, P40 or a little more.

Next I get a blue screen before getting any further and losing it all.

The number which had the P40 or so was probably a C167 and a little up the list.

Continuing with it right now and it could well have been a P47 here, making it a quite large one.

storflyt32 · 2016-12-12, 18:02

Noticing the following by pure chance.

http://factordb.com/index.php?id=1100000000618559631

According to the yafu ecm command, the remaining number here is in fact composite.

131182 digits, to be more precise.

Same old problem once again, or should I believe the result output?

No factors yet, only the given fact being mentioned or given.

Suggestions welcome.

Batalov · 2016-12-12, 21:46

Quote:

Originally Posted by storflyt32

Noticing the following by pure chance.

http://factordb.com/index.php?id=1100000000618559631

According to the yafu ecm command, the remaining number here is ~~in fact composite~~.

It is a known PRprime (2^435808+1)/(2^32+1)
A repunit in base -2³².

storflyt32 · 2016-12-12, 22:26

Also not prime when using isprime(ans) for the number again with Yafu.

This is probably the thing to be noticed here since as you mention, this number is a PRP only and not a P (or prime).

But assumedly there also should be given the fact that most of the numbers which turns out PRP next becomes P as the end result.

But perhaps there could still be exceptions to this fact?

2016-11-16, 08:59	#276
storflyt32 Feb 2013 2·229 Posts	Can you really have the factors of RSA-1024 without having to factorize it? We all know that it should not be possible. http://factordb.com/index.php?id=1100000000882813413 Notice that this is another number than the mentioned RSA-1024. But this number will probably not be factorized either. But I could possibly do so if I will, because here I ended up with the individual factors. Still working on this, of course. Thanks for the suggestion, by the way. https://en.wikipedia.org/wiki/Coppersmith_method https://en.wikipedia.org/wiki/Coppersmith%27s_attack I am able to find two selected links for the given suggestion. Any better suggestions for the correct one would be welcome. Last fiddled with by storflyt32 on 2016-11-16 at 09:07

2016-12-04, 17:47	#281
storflyt32 Feb 2013 2·229 Posts	http://factordb.com/index.php?id=1100000000885545955 http://factordb.com/index.php?id=1100000000885687682 http://factordb.com/index.php?id=1100000000885687293 Should tell that I was unfortunate to have it blow this time when pressing ^C and next having the window close in front of me. I did in fact have both the smaller factors here, even though the second one took quite some time to get at. But perhaps you already guessed the answer here. Not that small in fact when it comes to the first of the links, because even though the server, or maybe someone else in between did this one, I was able to factor it using the brute method, but next letting it run once again, this time by means of ecm. Using ecm with 2^21 curves did not work out, so I tried using 2^22 curves instead. The factors were found after 858340 of 4194304 curves, making this a quite heavy one. Next I did not report it, but it did take quite a long time. Once again we are apparently back at an incomplete result where the number in question most likely is not able to become factored. I leave it for someone else to decide whether or not this should be updated, but at least you should now be able to know the factors. Edit: Could give it yet another try, but it could take a day or more before getting the result. Last fiddled with by storflyt32 on 2016-12-04 at 17:58

2016-12-12, 03:43	#282
storflyt32 Feb 2013 2×229 Posts	Did not extend or include the last one down to the smaller factors. http://factordb.com/index.php?id=1100000000411903471 But I happened to read around here during the past weekend and noticed the P83 in this number. When such a thing happens, a little more should be attempted. With a disc borking as well, this became slightly difficult, but apparently adding both the P29 and P30 here. Also adding the P41 and next the P86, making for a complete factorization. But also should be noted by possibly knowing the two P90 factors of a C180 does not necessarily return a desired result when it comes to the rest, so when this is the case, I rather prefer to make a note of it when the remaining factors are of some size. As an example, take the product of the P83 and P86 and give the rest a try. http://factordb.com/index.php?id=1100000000886975937 I could leave it running overnight and have a look at it tomorrow. Last fiddled with by storflyt32 on 2016-12-12 at 03:48

2016-12-12, 15:15	#283
storflyt32 Feb 2013 2·229 Posts	Returning back to the computer, the second link had run out and another number being computed had found a quite larger factor, P40 or a little more. Next I get a blue screen before getting any further and losing it all. The number which had the P40 or so was probably a C167 and a little up the list. Continuing with it right now and it could well have been a P47 here, making it a quite large one. Last fiddled with by storflyt32 on 2016-12-12 at 15:15

2016-12-12, 18:02	#284
storflyt32 Feb 2013 1CA₁₆ Posts	Noticing the following by pure chance. http://factordb.com/index.php?id=1100000000618559631 According to the yafu ecm command, the remaining number here is in fact composite. 131182 digits, to be more precise. Same old problem once again, or should I believe the result output? No factors yet, only the given fact being mentioned or given. Suggestions welcome. Last fiddled with by storflyt32 on 2016-12-12 at 18:30

2016-11-18, 04:50	#278
storflyt32 Feb 2013 2·229 Posts	Thanks for the link. http://factordb.com/index.php?id=1100000000193628325 Not prime (when using isprime in Yafu).

2016-11-21, 12:15	#279
storflyt32 Feb 2013 458₁₀ Posts	http://factordb.com/index.php?id=1100000000883308511 Not for free. Took quite a while to do this one. Became a PRP120 first, next a P120 in the final output. Total factoring time = 81701.2252 seconds

2016-11-25, 22:17	#280
storflyt32 Feb 2013 2×229 Posts	http://factordb.com/index.php?id=1100000000884781588 One less to go. Digging a little deeper here, this took quite a while to get at.

2016-12-12, 22:26	#286
storflyt32 Feb 2013 2×229 Posts	Also not prime when using isprime(ans) for the number again with Yafu. This is probably the thing to be noticed here since as you mention, this number is a PRP only and not a P (or prime). But assumedly there also should be given the fact that most of the numbers which turns out PRP next becomes P as the end result. But perhaps there could still be exceptions to this fact?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Can Pollard Rho cycles be used to find a factor?	wwf	Factoring	26	2013-09-30 04:24
PFGW can't find a small factor.	Arkadiusz	Software	7	2013-02-18 12:43
Chance to find an n-digit factor with ECM	RedGolpe	Factoring	4	2007-03-23 15:24
How much ECM does it take to find a given factor?	geoff	Factoring	5	2004-09-29 20:14
Where I find the best program to it factor keys? I use AMD.	chrow	Factoring	5	2004-02-19 10:15