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

[bsquared]

Originally Posted by storm5510

The rule of digits I memorized, 2 * log(2) * 1277 indicates 768 digits. Is the implication here meaning this exponent has no factor, or is it saying that current factoring software cannot run it?

M(1277) has 385 digits (log10(2) * 1277). It can and will be factored, probably by SNFS.

[VBCurtis]

Originally Posted by bsquared

M(1277) has 385 digits (log10(2) * 1277). It can and will be factored, probably by SNFS.

Two amplifications:
SNFS "probably" because there remains a small chance that we find a factor by ECM and avoid SNFS.

The software can handle this job, but the hardware requirements are difficult. See this thread for a discussion about just how difficult:
https://mersenneforum.org/showthread.php?t=23280
Short summary: Something like 10,000 thread-years for the sieve part of the job (can be split among any number of machines), and 500-800 thread-years on a single cluster for the matrix.

[dcheuk]

I feel like such an idiot, I have no idea what you guys are talking about and why, yet I uses PGP encryption.

Shame on me. Time to hit wikipedia.

[ixfd64]

Ryan Propper: hold my beer.

[ewmayer]

Originally Posted by bsquared

M(1277) has 385 digits (log10(2) * 1277). It can and will be factored, probably by SNFS.

This Wikipedia entry on integer factorization methods may be helpful:

"All unfactored parts of the numbers 2^n − 1 with n between 1000 and 1200 were factored by a multiple-number-sieve approach in which much of the sieving step could be done simultaneously for multiple numbers, by a group including T. Kleinjung, J. Bos and A. K. Lenstra, starting in 2010.[11] To be precise, n=1081 was completed on 11 March 2013; n=1111 on 13 June 2013; n=1129 on 20 September 2013; n=1153 on 28 October 2013; n=1159 on 9 February 2014; 1177 on May 29, 2014, n=1193 on 22 August 2014, and n=1199 on December 11, 2014; the first detailed announcement was made in late August 2014. The total effort for the project is of the order of 7500 CPU-years on 2.2 GHz Opterons, with roughly 5700 years spent sieving and 1800 years on linear algebra."

They may well be working on the next batch-interval, which would likely include M1277.

[storm5510]

Originally Posted by bsquared

M(1277) has 385 digits (log10(2) * 1277). It can and will be factored, probably by SNFS.

Base 10 logarithm * 2. I didn't remember it as well as I thought.

I looked at MadPoo's stats page for this exponent. It is extensive. He performed one LL test which returned a non-zero residue. The B1's on the ECM page are pretty large.

If no one minds me asking, what is SNFS?

[a1call]

Special number field sieve

I looked it up:

https://encyclopedia.thefreedictiona...er+Field+Sieve

[jdcs]

Originally Posted by bsquared

M(1277) has 385 digits (log10(2) * 1277). It can and will be factored, probably by SNFS.

Yup. M1277 is exactly

2,601,983,048,666,099,770,481,310,081,841,021,384,653,815,561,816,676,201,329,778,087,600,902,014,918,340,074,503,059,860,433,081,046,210,605,403,488,570,251,947,845,891,562,080,866,227,034,976,651,419,330,190,731,032,377,347,305,086,443,295,837,415,395,887,618,239,855,136,922,452,802,923,419,286,887,119,716,740,625,346,109,565,072,933,087,221,327,790,207,134,604,146,257,063,901,166,556,207,972,729,700,461,767,055,550,785,130,256,674,608,872,183,239,507,219,512,717,434,046,725,178,680,177,638,925,792,182,271

No one has been able to factor it.

Originally Posted by storm5510

He performed one LL test which returned a non-zero residue.

Here, I'll run another primality test on M1277 for you right now :) If M1277 were prime, then 3^M1277−1 divided by M1277 would leave a remainder of 1. It actually leaves a remainder of

130097009096122762767473496823255434540228984414867314726919886268610160501252081222324599697844605869576180512060962284431294253935654006585706254158430724720116673242880501921958212033147654921548617527557262672869012971858652641220348593990571013266358030220764922030155567036015710551658146991088104859280673740017817157307545503137271422771876384656160606106020300514092161045741

so M1277 is definitely not prime. (This test took .00000000139 CPU years on my computer.)

Originally Posted by dcheuk

I feel like such an idiot, I have no idea what you guys are talking about and why, yet I uses PGP encryption.

Yeah, PGP is pretty cool. You can import my key above and try encrypting a message to me.

The 30-second explanation:

• To encrypt a message to me, take your message m (converted into number), multiply it by itself 65,537 times, and divide it by M1277. The remainder is the encrypted message.
• To decrypt the message ... mwhahahaha -- no one will ever be able to decrypt it.

Originally Posted by VBCurtis

The software can handle this job

Never! The world will never know the factors of M1277.

[storm5510]

Originally Posted by jdcs

Never! The world will never know the factors of M1277.

Perhaps not with the hardware we have now.

I found a web site which will run ECM's by incrementing the B1 and B2 values, and desired number of curves, as it runs.

https://www.alpertron.com.ar/ECM.HTM

I gave it M1277 in the form of (2^1277) - 1. It presented the 385 digit equivalent shown above. As far as I can tell, it never stops, unless a person stops it. It remembers where it left off when restarted. I don't know if its B1 has a ceiling. A chart shows a possible B1 of 2.9-billion.

I suppose this is all well-and-good if a person has an extra decade, or more, to simply let it run.

[ewmayer]

Originally Posted by jdcs

Never! The world will never know the factors of M1277.

Better trolls, please - The Wikiarticle snippet I gave above shows SNFS already did all remaining M-numbers with p < 1200 over 5 years ago ... p = 1277 is only a modest increment above that. Like I said, I suspect the same team is doing the needed several years' worth of batch-sieving the next range of exponents, which likely includes 1277. The approach is different from earlier SNFS sieving implementations, in that one does more sieving work up front, but on multiple moduli at the same time, i.e. the total sieving work ends up being less. The risk of course is that ECM might turn up factors on one or more of the moduli being tackled before the sieving completes, thus rendering part of the sieving effort a waste, but I expect the folks doing the SNFS have a pretty good understanding of probabilities as regards the likelihood of such ECM successes.

[jdcs]

Originally Posted by ewmayer

Better trolls, please - The Wikiarticle snippet I gave above shows SNFS already did all remaining M-numbers with p < 1200 over 5 years ago.

And the paper explicitly blames you guys for making them do it!

"Given long-term projects such as [10, 11, 6] where many factoring enthusiasts worldwide constantly busy themselves to factor many special numbers, such as for instance small-radix repunits, it makes sense to investigate whether factoring efforts that are eagerly pursued no matter what can be combined to save on the overall amount of work."