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

storm5510 · 2019-09-20, 15:36

Allow me to deviate here just a little:

M1277 is 385 digits in length. So, in bits, this would be 3,080, given that each digit would be represented by 8 bits.

There must be something I am missing. Last year, Luigi Morelli completely reworked this old factor5 program into factor5j. It is extremely fast. He designed it to run exponents in ranges to find factors. Unlike Prime95 and mfaktc, factoring limits are expressed in k values.

A sample command line would look like this:

Code:

factor5j -e 1001 -E 4999 -k 1 -K 90

Lower case characters represent starting values and upper case ending values. Exponents with factors are displayed on the screen, along with their factor and the k value where the factor was found. All results go into a results text file, factors and no factors.

So, I tried 1277.

Code:

factor5j -e 1277 -E 1277 -k 1 -K 90

In the time it took me to press the enter key, it displayed the following:

Code:

Tested 1 exponents over N[1277..1277] and K[1..90] - found 0 factors.

I incremented the ending k value into many hundreds. The result was always the same. No factors. This program is available in James Heinrich's archive on mesenne.ca. A LL test says there is a factor. Perhaps in the future, said factor can be written into a text file. The residue does not give much of an indication as to what the factor actually is.

hansl · 2019-09-20, 18:00

k=90 is nothing... even several hundred is nothing

log2(2*90*1277+1) ~= 17.81 bit depth that you just TF'd to. Its not surprising that it takes 0 time.

1277 has been TF'd up to 2^67 so far with no results.
That's about 642,013,880,517,689 times the effort of going to k=90.

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

Also

Quote:

Originally Posted by storm5510

M1277 is 385 digits in length. So, in bits, this would be 3,080, given that each digit would be represented by 8 bits.

Base-256 encoding of Base-10 digits is a very unnatural way to represent it. In bits, its just 1277 length.

edit3: Also, having done a substantial amount of TF in the upper range of exponents (> 1e9), I don't mean to slam on Luigi's efforts but I've found factor5j to be...inaccurate. It misses many actual factors.

storm5510 · 2019-09-20, 21:53

Quote:

Originally Posted by hansl

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

Also, having done a substantial amount of TF in the upper range of exponents (> 1e9), I don't mean to slam on Luigi's efforts but I've found factor5j to be...inaccurate. It misses many actual factors.

Thank you for the clarification.

For now, it looks like ECM is the game. A member here wrote several year ago that this is like throwing darts at a board from 30 feet.

LaurV · 2019-09-21, 03:36

Just to clarify, what Luigi (and all contributors to his project) is doing (with factor5 and mmff, etc) is about "double" mersenne numbers, which are much larger, different type of monsters. But the other discussion stands right.

I somehow like how this thread progressed, regardless of the fact that it started more like a joke, but leave to mathematicians and nerds to transform any joke in a serious discussion, and (as other threads prove) make a joke from a serious topic.

On the other hand, like Retina used to say, the easiest way to get somebody else do work for you, is to claim that the work can not be done. @OP, you do not need to do that here, there are lots of efforts (and people) involved in factoring low mersenne numbers and filling cunnigham tables, and we'll pass this little threshold with or without your help. It will just take a little while more...

I would bet my life on this.

storm5510 · 2019-09-22, 14:59

This could be considered off-topic and I apologize if it is.

Regarding ECM's. I look at the progress page on mersenne.org and I see spreadsheet type charts. Contained in the majority of cells is the word "Done." Prime95 appears to use very large random seed values when running ECM's.

My question is this: How can any of this be considered done when it is all based on random numbers?

hansl · 2019-09-22, 15:10

For a given bound there is a certain probability that doing X number of curves will find a factor of Y digits or less. After you do so many curves, its not worth it to keep doing that same bound, and its better to increase the bound etc.

This page shows some optimal bounds for gmp-ecm and explains in a little more detail: https://members.loria.fr/PZimmermann...cm/params.html

PhilF · 2019-09-22, 15:12

It's the B1 value that you need to pay attention to when looking at the columns.

On M1277 for example, the 60 digit level has been done, which means the B1=260000000 level is done. We are now approximately 190,450 curves (of the 360,000 required) into the 65 digit level, which is the B1=800000000 level.

The random seed, or sigma, is purely random and doesn't pertain to the bit level.

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.

a1call · 2019-09-22, 21:49

Sounds like M1277 encrypted file would be an ideal e-Time-Capsule. You wouldn't know when it can be decrypted.
Too bad time capsules are not nearly as interesting as people who put them together think they are.

storm5510 · 2019-09-22, 22:18

Quote:

Originally Posted by PhilF

It's the B1 value that you need to pay attention to when looking at the columns.

On M1277 for example, the 60 digit level has been done, which means the B1=260000000 level is done. We are now approximately 190,450 curves (of the 360,000 required) into the 65 digit level, which is the B1=800000000 level.

The random seed, or sigma, is purely random and doesn't pertain to the bit level.

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.

I believe the air is starting to finally clear somewhat. So, regardless of how large the B1 value is, the bit level would begin very low and proceed upwards from there?

PhilF · 2019-09-22, 22:32

Quote:

Originally Posted by storm5510

I believe the air is starting to finally clear somewhat. So, regardless of how large the B1 value is, the bit level would begin very low and proceed upwards from there?

I don't like the way that is worded.

The larger B1 is, the more optimized the curves are for finding larger factors (B1=800,000,000 for a 65 digit factor, for example), but they can still find the smaller factors too. That's one of the reasons why after a certain number of curves have been run at a certain level you move on, because even on the remote chance a factor was missed, it will likely be found later by a curve optimized for a larger factor.

LaurV · 2019-09-23, 05:58

When you say a level was "done" it only means that the probability of a factor being below that level decreased under a limit value (i.e. it became very-very-VERY small). It all has to do with the probability of a number of a given size being "smooth".

Right now, the only warranty we have is that there is no factor under 2^66 or so, due to the fact that TF to that level is somehow double-checked by TJAOI's activity. Somebody already made TF to 2^67, but that is not double-checked, and there is a minuscule probability that something went wrong with that test, unintentional or not. Without trying to blame or accuse anybody, we had cases in the past where people reported fake TF results for lower expos, for credit. That is because, first of all, the "TF credit" here is huge (it gets higher as the exponent gets smaller), and second, due to huge quantity of P-1 and ECM done in this range, the probability of a factor to exist below, say, 2^80, it is almost zero (like in zero followed by decimal point, and another 10 or 20 zeros, than a 1, or so), and one can get the "huge credit for free". I mean, I could technically report "no factor to z bits" by myself, where z is anything below 80, and get billions of GHzDays credits, and yet have an almost-zero risk that somebody proves me wrong (i.e. a cheater).

Now, this is only a theoretic discussion, and it is NOT an invitation or suggestion for you (general you) to do so!

TF, assuming properly (and honestly) done, will find any possible factor below a limit. Right now, that limit is 2^67, which is also double-checked to 2^66 or so, by TJAOI's work.

But then, Pm1 and ECM do not find all factors below a limit, only factors with a special property (being power-smooth) will be found.

TF is like taking a surface, and placing a black dot on it. Under the black dot there is no gold to dig, anymore. All gold was dug up. Then, you can imagine Pm1 and ECM like a big dark shadow that is slowly spreading from this dot, moving into the factors' territory, covering it with darker and darker... dark

The light gray area at the "border" of the shadow still may contain a lot of undiscovered factors, but the darker gray situated more "inside" of the shadow, closer to the black dot in the center, covered most of the candidates and there are less and less probable that any undiscovered factor lies there. But the probability is not zero. Doing more and more "curves", and/or doing Pm1 with larger bounds is like shadowing more and more of the surface, each darken or not darken part becomes darker. Few areas around the initial black disk become totally black. But there is a lot of gray area, and the gray is getting lighter as you go away from the black dot.

I hope this fixes it

2019-09-20, 15:36	#23
storm5510 Random Account Aug 2009 3²×7×31 Posts	Allow me to deviate here just a little: M1277 is 385 digits in length. So, in bits, this would be 3,080, given that each digit would be represented by 8 bits. There must be something I am missing. Last year, Luigi Morelli completely reworked this old factor5 program into factor5j. It is extremely fast. He designed it to run exponents in ranges to find factors. Unlike Prime95 and mfaktc, factoring limits are expressed in k values. A sample command line would look like this: Code: factor5j -e 1001 -E 4999 -k 1 -K 90 Lower case characters represent starting values and upper case ending values. Exponents with factors are displayed on the screen, along with their factor and the k value where the factor was found. All results go into a results text file, factors and no factors. So, I tried 1277. Code: factor5j -e 1277 -E 1277 -k 1 -K 90 In the time it took me to press the enter key, it displayed the following: Code: Tested 1 exponents over N[1277..1277] and K[1..90] - found 0 factors. I incremented the ending k value into many hundreds. The result was always the same. No factors. This program is available in James Heinrich's archive on mesenne.ca. A LL test says there is a factor. Perhaps in the future, said factor can be written into a text file. The residue does not give much of an indication as to what the factor actually is.

2019-09-21, 03:36	#26
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	Just to clarify, what Luigi (and all contributors to his project) is doing (with factor5 and mmff, etc) is about "double" mersenne numbers, which are much larger, different type of monsters. But the other discussion stands right. I somehow like how this thread progressed, regardless of the fact that it started more like a joke, but leave to mathematicians and nerds to transform any joke in a serious discussion, and (as other threads prove) make a joke from a serious topic. On the other hand, like Retina used to say, the easiest way to get somebody else do work for you, is to claim that the work can not be done. @OP, you do not need to do that here, there are lots of efforts (and people) involved in factoring low mersenne numbers and filling cunnigham tables, and we'll pass this little threshold with or without your help. It will just take a little while more... I would bet my life on this. Last fiddled with by LaurV on 2019-09-22 at 05:32 Reason: grrr those line spacing

2019-09-22, 15:12	#29
PhilF Feb 2005 Colorado 2²·7·23 Posts	It's the B1 value that you need to pay attention to when looking at the columns. On M1277 for example, the 60 digit level has been done, which means the B1=260000000 level is done. We are now approximately 190,450 curves (of the 360,000 required) into the 65 digit level, which is the B1=800000000 level. The random seed, or sigma, is purely random and doesn't pertain to the bit level. 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. Last fiddled with by PhilF on 2019-09-22 at 15:15

2019-09-23, 05:58	#33
LaurV Romulan Interpreter Jun 2011 Thailand 258B₁₆ Posts	When you say a level was "done" it only means that the probability of a factor being below that level decreased under a limit value (i.e. it became very-very-VERY small). It all has to do with the probability of a number of a given size being "smooth". Right now, the only warranty we have is that there is no factor under 2^66 or so, due to the fact that TF to that level is somehow double-checked by TJAOI's activity. Somebody already made TF to 2^67, but that is not double-checked, and there is a minuscule probability that something went wrong with that test, unintentional or not. Without trying to blame or accuse anybody, we had cases in the past where people reported fake TF results for lower expos, for credit. That is because, first of all, the "TF credit" here is huge (it gets higher as the exponent gets smaller), and second, due to huge quantity of P-1 and ECM done in this range, the probability of a factor to exist below, say, 2^80, it is almost zero (like in zero followed by decimal point, and another 10 or 20 zeros, than a 1, or so), and one can get the "huge credit for free". I mean, I could technically report "no factor to z bits" by myself, where z is anything below 80, and get billions of GHzDays credits, and yet have an almost-zero risk that somebody proves me wrong (i.e. a cheater). Now, this is only a theoretic discussion, and it is NOT an invitation or suggestion for you (general you) to do so! TF, assuming properly (and honestly) done, will find any possible factor below a limit. Right now, that limit is 2^67, which is also double-checked to 2^66 or so, by TJAOI's work. But then, Pm1 and ECM do not find all factors below a limit, only factors with a special property (being power-smooth) will be found. TF is like taking a surface, and placing a black dot on it. Under the black dot there is no gold to dig, anymore. All gold was dug up. Then, you can imagine Pm1 and ECM like a big dark shadow that is slowly spreading from this dot, moving into the factors' territory, covering it with darker and darker... dark The light gray area at the "border" of the shadow still may contain a lot of undiscovered factors, but the darker gray situated more "inside" of the shadow, closer to the black dot in the center, covered most of the candidates and there are less and less probable that any undiscovered factor lies there. But the probability is not zero. Doing more and more "curves", and/or doing Pm1 with larger bounds is like shadowing more and more of the surface, each darken or not darken part becomes darker. Few areas around the initial black disk become totally black. But there is a lot of gray area, and the gray is getting lighter as you go away from the black dot. I hope this fixes it Last fiddled with by LaurV on 2019-09-23 at 06:03

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
I want to factorize 2^1277-1	tanaydin	Information & Answers	29	2018-05-14 01:09
Question: Is Our Forum Secure in Some Areas	9021951	Information & Answers	7	2011-11-02 23:29
World Cup Soccer	davieddy	Hobbies	111	2011-05-28 19:21
Plans for the end of the world	Oddball	Lounge	4	2011-04-18 04:06
Change the world!	Xyzzy	Lounge	5	2009-08-31 12:41

2019-09-22, 14:59	#27
storm5510 Random Account Aug 2009 3²×7×31 Posts	This could be considered off-topic and I apologize if it is. Regarding ECM's. I look at the progress page on mersenne.org and I see spreadsheet type charts. Contained in the majority of cells is the word "Done." Prime95 appears to use very large random seed values when running ECM's. My question is this: How can any of this be considered done when it is all based on random numbers?

2019-09-22, 15:10	#28
hansl Apr 2019 205₁₀ Posts	For a given bound there is a certain probability that doing X number of curves will find a factor of Y digits or less. After you do so many curves, its not worth it to keep doing that same bound, and its better to increase the bound etc. This page shows some optimal bounds for gmp-ecm and explains in a little more detail: https://members.loria.fr/PZimmermann...cm/params.html

2019-09-22, 21:49	#30
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3·5·137 Posts	Sounds like M1277 encrypted file would be an ideal e-Time-Capsule. You wouldn't know when it can be decrypted. Too bad time capsules are not nearly as interesting as people who put them together think they are.