Behold, "The World's Most Secure RSA key"®©™ : 2^1277-1

[storm5510]

Originally Posted by PhilF

I am currently running curves on M1277 myself, using Prime95 for stage 1, with both B1 and B2 set at 800000000. Stage 2 is being run by GMP-ECM, and by using the -k 2 option when invoking it I am getting a B2 bounds of 25,992,573,767,178.

GMP-ECM seemed familiar so I checked. I had it stored on an external hard drive. It is a Windows build. I don't know from Linux. Despite looking at the short readme document, I could not get it do much of anything.

Originally Posted by LaurV

TF is like taking a surface, and placing a black dot on it. Under the black dot there is no gold to dig, anymore...

After a while, TF becomes a cumbersome process. I still have Luigi's original Factor5 program. I started it on M1277. After a short time, I looked at the percentage complete and the time it used then made some rough calculations. I came up with 6.6 years. No way! It will have to stay at 2⁶⁷.

Originally Posted by LaurV

I hope this fixes it...

It does. You wrote a lot and I really appreciate your effort.

@hansl I saved the web page you linked as an HTML file. I found it to be quite useful in understanding this process more.

[PhilF]

Originally Posted by storm5510

GMP-ECM seemed familiar so I checked. I had it stored on an external hard drive. It is a Windows build. I don't know from Linux. Despite looking at the short readme document, I could not get it do much of anything.

I don't have the development tools loaded on my current Windows 10 system, so instead of compiling from source I grabbed this Windows binary, courtesy of Dylan14. It is compiled for the Intel Skylake architecture, and I have a Coffee Lake which is very similar:

https://www.mersenneforum.org/showthread.php?p=513979

Here's a great write-up on how to use it courtesy of lycorn:

https://www.mersenneforum.org/showthread.php?p=400703

[storm5510]

Originally Posted by PhilF

...It is compiled for the Intel Skylake architecture, and I have a Coffee Lake which is very similar:

https://www.mersenneforum.org/showthread.php?p=513979

Here's a great write-up on how to use it courtesy of lycorn:

https://www.mersenneforum.org/showthread.php?p=400703

I have a Kaby Lake and it seems to start this one alright.

Perhaps you could give some examples of command-line inputs. That might help.

[PhilF]

Originally Posted by storm5510

I have a Kaby Lake and it seems to start this one alright.

Perhaps you could give some examples of command-line inputs. That might help.

Here's the command line I use:

ecm -v -k 2 -timestamp -resume ecm-in.txt -save ecm-out.txt 8e08-8e08

This is after placing Prime95's output (from results.txt) into ecm-in.txt.

Lycorn's post outlines all the steps pretty well.

[storm5510]

In the wee hours of this morning before hitting the rack, I found a different instruction document for GMP-ECM. It contains most of the information in the readme file in the archive. Its layout is far easier for my old eyes to read. I need that.

Originally Posted by hansl

...2^67 is equivalent to k=57,781,500,622,426,160

A question: What is the relationship between k values and powers of 2? There must be some type of conversion...

[retina]

Originally Posted by storm5510

A question: What is the relationship between k values and powers of 2? There must be some type of conversion...

2^67 = 2*k*p, k = 57781500622426160, p = 1277

[bsquared]

Originally Posted by storm5510

In the wee hours of this morning before hitting the rack, I found a different instruction document for GMP-ECM. It contains most of the information in the readme file in the archive. Its layout is far easier for my old eyes to read. I need that.



A question: What is the relationship between k values and powers of 2? There must be some type of conversion...

Factors of Mersenne numbers must have the form 2*k*q+1, where q is the exponent.
2^67 is approximately 2*(57,781,500,622,426,160)*1277+1
So, factoring to the "67-bit level" or to "k=57,781,500,622,426,160" are equivalent statements when q=1277

[edit]
ECM testing has effectively performed trial division up to about the 200 bit level (we can be reasonably sure there are no factors smaller than 60 digits in 2^1277-1). This is equivalent to k=629184825473371290345325799663728505294519574699605652036

[storm5510]

Originally Posted by bsquared

Factors of Mersenne numbers must have the form 2*k*q+1, where q is the exponent.
2^67 is approximately 2*(57,781,500,622,426,160)*1277+1
So, factoring to the "67-bit level" or to "k=57,781,500,622,426,160" are equivalent statements when q=1277

[edit]
ECM testing has effectively performed trial division up to about the 200 bit level (we can be reasonably sure there are no factors smaller than 60 digits in 2^1277-1). This is equivalent to k=629184825473371290345325799663728505294519574699605652036

Alright, the absolute value of 2⁶⁷ = 147,573,952,589,676,412,928‬ via Windows 10 Calculator. I think what I was trying to do is to not use an exponent, like 2¹²⁷⁷-1, to come up an equivalency for k as it related to 2^x. A person would have to pick some exponent to make this work. I am still not sure how the bold number in the quote above is arrived at. Too tired perhaps...

[bsquared]

Originally Posted by storm5510

Alright, the absolute value of 2⁶⁷ = 147,573,952,589,676,412,928‬ via Windows 10 Calculator. I think what I was trying to do is to not use an exponent, like 2¹²⁷⁷-1, to come up an equivalency for k as it related to 2^x. A person would have to pick some exponent to make this work. I am still not sure how the bold number in the quote above is arrived at. Too tired perhaps...

Retina stated it simply just above my post.

2^67 = 2*k*p.

p=1277

solve for (integer) k = 2^67 / (2p).

k = 57781500622426160

So that's where k comes from, for the specific example of 2¹²⁷⁷-1. You are correct that you have to use the exponent to relate the size of a factor, in bits, to k, because all factors have the form 2*k*p+1.

[storm5510]

Originally Posted by bsquared

Retina stated it simply just above my post.

2^67 = 2*k*p.

p=1277

solve for (integer) k = 2^67 / (2p).

k = 57781500622426160

So that's where k comes from, for the specific example of 2¹²⁷⁷-1. You are correct that you have to use the exponent to relate the size of a factor, in bits, to k, because all factors have the form 2*k*p+1.

147,573,952,589,676,412,928‬ / 2,554 = 57,781,500,622,426,160.

Now I get it. A simple rearrangement of the formula, more or less.

I will leave this alone now. Thank you all for helping my old dumb a** learn something.

[a1call]

Is decripting-computation-cost a function of high cost of Modular-Exponentiation?

Would it be easier/easy to decrypt an RSA encrypted message if you could perform significantly faster Modular-Exponentiation than is possible now, without knowing the private key?

Thanks in advance.