mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-06-02, 13:04   #1
BigNumberGuy
 
May 2022

3×7 Posts
Exclamation 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?
BigNumberGuy is offline   Reply With Quote
Old 2022-06-02, 14:44   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1142710 Posts
Default

Quote:
Originally Posted by BigNumberGuy View Post
[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.
xilman is offline   Reply With Quote
Old 2022-06-02, 14:52   #3
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

100011000012 Posts
Default

Less than 350 digits . 10 +/- years is my guess.
rudy235 is offline   Reply With Quote
Old 2022-06-02, 15:24   #4
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

32·11·23 Posts
Default

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.
storm5510 is offline   Reply With Quote
Old 2022-06-02, 17:19   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×769 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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).

Last fiddled with by VBCurtis on 2022-06-02 at 17:19
VBCurtis is offline   Reply With Quote
Old 2022-06-02, 17:44   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×7×283 Posts
Default

Quote:
Originally Posted by rudy235 View Post
Less than 350 digits . 10 +/- years is my guess.
It is 385 decimal digits in size.
Batalov is offline   Reply With Quote
Old 2022-06-02, 17:51   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

3×13×293 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 is offline   Reply With Quote
Old 2022-06-02, 17:54   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

3·13·293 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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?
xilman is offline   Reply With Quote
Old 2022-06-02, 22:02   #9
charybdis
 
charybdis's Avatar
 
Apr 2020

81410 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2022-06-03, 00:05   #10
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

46116 Posts
Default

Quote:
Originally Posted by Batalov View Post
It is 385 decimal digits in size.
I stand corrected! Damn my dyslexia! I had it as 1+348. Rather than 1 +384

Last fiddled with by rudy235 on 2022-06-03 at 00:39 Reason: dYslexia.
rudy235 is offline   Reply With Quote
Old 2022-06-03, 00:36   #11
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

7·17·89 Posts
Default

Quote:
Originally Posted by rudy235 View Post
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.

Last fiddled with by chalsall on 2022-06-03 at 00:37
chalsall is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 01:02.


Tue Aug 16 01:02:03 UTC 2022 up 39 days, 19:49, 1 user, load averages: 1.56, 1.29, 1.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”