About M1277

BigNumberGuy · 2022-06-02, 13:04

[NEWCOMER ALERT]
I was messing around in mersenne.ca and saw that M1277 was the smallest composite number with no factor, and all of TF, P-1 and ECM had been done to a high degree.
Is it likely that we will factor M1277 in the next, say, 5-10 years? what about 20 years?

xilman · 2022-06-02, 14:44

Quote:

Originally Posted by BigNumberGuy

[NEWCOMER ALERT]
I was messing around in mersenne.ca and saw that M1277 was the smallest composite number with no factor, and all of TF, P-1 and ECM had been done to a high degree.
Is it likely that we will factor M1277 in the next, say, 5-10 years? what about 20 years?

Who knows?

I would be surprised if it takes 20 years.

rudy235 · 2022-06-02, 14:52

Less than 350 digits . 10 +/- years is my guess.

storm5510 · 2022-06-02, 15:24

A lot of people have done a lot of work on M1277. More than likely, far more than what has been turned in to the network servers. Some ran ECM stage 1 with Prime95 and stage 2 with GMP-ECM. I tried it myself probably three or four years ago. It was an extremely slow process. Even increasing the trial factoring by one bit was going to take weeks.

My guess about time: More than five years. Perhaps 10. The hardware does not exist yet and neither does the programming. I have no idea what that might look like.

VBCurtis · 2022-06-02, 17:19

Quote:

Originally Posted by storm5510

The hardware does not exist yet and neither does the programming.

False, and false. Just because the hardware on your desk isn't sufficient, concluding the hardware does not exist is plain wrong. Software is easy: CADO is sufficient to factor it- the CADO team factored numbers of size 2^1200 already, and one can peruse their paper on those jobs to learn what hardware requirements there were at that size and then scale RAM needs for the bigger input size.

For those merely curious about scale rather than details, a sieve process might need 60-80GB of ram to run and the matrix might need a 1TB ram machine for the CADO matrix solving style, or a cluster totaling 1-1.5TB ram if using msieve for the matrix.

SNFS jobs such as 2^1277-1 double in CPU-years difficulty roughly every 30 bits, so this job would take ~8 times longer than 2^1190 (a size that has been factored already by the CADO team).

Batalov · 2022-06-02, 17:44

Quote:

Originally Posted by rudy235

Less than 350 digits . 10 +/- years is my guess.

It is 385 decimal digits in size.

xilman · 2022-06-02, 17:51

Quote:

Originally Posted by Batalov

It is 385 decimal digits in size.

Way beyond plausible ECM, though as noted above, within range of current SNFS.

Assuming a 1/3 - 2/3rd split, which is close to an optimal assumption absent any further information, the smaller factor would be around 130 digits. Current record is well under 100 digits.

xilman · 2022-06-02, 17:54

Quote:

Originally Posted by VBCurtis

False, and false. Just because the hardware on your desk isn't sufficient, concluding the hardware does not exist is plain wrong. Software is easy: CADO is sufficient to factor it- the CADO team factored numbers of size 2^1200 already, and one can peruse their paper on those jobs to learn what hardware requirements there were at that size and then scale RAM needs for the bigger input size.

It would be easy enough, though largely futile, to perform some trial sieving on a desktop machine.

You don't need to hold all the primes and sieve array in RAM if what you want to do is determine yields. Performance would be pathetic, but so what?

charybdis · 2022-06-02, 22:02

M1277 (SNFS 385) is very roughly 4 times as difficult as RSA-250 (GNFS 250), which took the CADO team 2700 CPU-years. So we're looking at about 10,000 CPU-years for M1277.

The hardware definitely exists. As for software, current CADO can probably handle it, but there's an upper limit of 2^31 for factor base primes, and this might add an extra thousand CPU-years or so. The CADO team have been working on extending the limit to 2^32 for a while.

rudy235 · 2022-06-03, 00:05

Quote:

Originally Posted by Batalov

It is 385 decimal digits in size.

I stand corrected! Damn my dyslexia! I had it as 1+348. Rather than 1 +384

chalsall · 2022-06-03, 00:36

Quote:

Originally Posted by rudy235

I stand corrected! Damn my dislexia!

Just between you and me (and everyone else reading this), it is OK to be dyslexic. Almost all are, but just don't yet realize it.

Being "on the spectrum" is actually nominal. Very few people are actually "normal".

It took me a very long time to figure this out.

Sincerely.

2022-06-02, 13:04	#1
BigNumberGuy May 2022 3×7 Posts	About M1277 [NEWCOMER ALERT] I was messing around in mersenne.ca and saw that M1277 was the smallest composite number with no factor, and all of TF, P-1 and ECM had been done to a high degree. Is it likely that we will factor M1277 in the next, say, 5-10 years? what about 20 years?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Predict the number of digits from within the factor for M1277	sweety439	Cunningham Tables	7	2022-06-11 11:04
Python script for search for factors of M1277 using random k-intervals	Viliam Furik	Factoring	61	2020-10-23 11:52
M1277 - no factors below 2^65?	DanielBamberger	Data	17	2018-01-28 04:21

2022-06-02, 14:52	#3
rudy235 Jun 2015 Vallejo, CA/. 10001100001₂ Posts	Less than 350 digits . 10 +/- years is my guess.

2022-06-02, 15:24	#4
storm5510 Random Account Aug 2009 Not U. + S.A. 2×1,123 Posts	A lot of people have done a lot of work on M1277. More than likely, far more than what has been turned in to the network servers. Some ran ECM stage 1 with Prime95 and stage 2 with GMP-ECM. I tried it myself probably three or four years ago. It was an extremely slow process. Even increasing the trial factoring by one bit was going to take weeks. My guess about time: More than five years. Perhaps 10. The hardware does not exist yet and neither does the programming. I have no idea what that might look like.

2022-06-02, 22:02	#9
charybdis Apr 2020 31D₁₆ Posts	M1277 (SNFS 385) is very roughly 4 times as difficult as RSA-250 (GNFS 250), which took the CADO team 2700 CPU-years. So we're looking at about 10,000 CPU-years for M1277. The hardware definitely exists. As for software, current CADO can probably handle it, but there's an upper limit of 2^31 for factor base primes, and this might add an extra thousand CPU-years or so. The CADO team have been working on extending the limit to 2^32 for a while.