mersenneforum.org > Data M1277 - no factors below 2^65?
 Register FAQ Search Today's Posts Mark Forums Read

2017-11-18, 04:55   #1
DanielBamberger

"Daniel Bamberger"
Nov 2017
Marburg, Germany

33 Posts
M1277 - no factors below 2^65?

I am trying to confirm the information given in https://en.wikipedia.org/wiki/Mersen...rsenne_numbers. It states:
Quote:
 As of October 2017, the Mersenne number M1277 is the smallest composite Mersenne number with no known factors; it has no prime factors below 265.
The page for 1277 on GIMPS shows that it has no known factors, but I can't see how it is determined that it has no factor below 265. From the "History" section, it seems that exponents between 257 and 258 have never been checked. Is this correct?

2017-11-18, 07:22   #2
xilman
Bamboozled!

May 2003
Down not across

23·32·139 Posts

Quote:
 Originally Posted by DanielBamberger I am trying to confirm the information given in https://en.wikipedia.org/wiki/Mersen...rsenne_numbers. It states: The page for 1277 on GIMPS shows that it has no known factors, but I can't see how it is determined that it has no factor below 265. From the "History" section, it seems that exponents between 257 and 258 have never been checked. Is this correct?
GIMPS is not the only project attempting to factor this number.

265 has only 20 digits. I don't know precisely how much ECM work has been done on 1277 but I'd guess that at least a t60 has been done by now. The chance of a factor exists with fewer than 40 digits is somewhere between nil and negligible and I for one would be astounded if a p4x were to show up.

 2017-11-18, 13:32 #3 ATH Einyen     Dec 2003 Denmark 2×3×11×43 Posts 42% of t65 has been done: https://www.mersenne.org/report_ecm/ So there is less than 37% chance/risk of a missed 60 digit factor, and very low chance/risk of a missed factor below 55 digits.
 2017-11-18, 17:51 #4 GP2     Sep 2003 1010000100102 Posts A lot of small exponents show a relatively small bit level for trial factoring, well below 64 bits. Nevertheless, it is absolutely not worthwhile to attempt trial factoring for them. There are two reasons for this: they have been very extensively ECM tested, and the work of user TJAOI. ECM testing is probabilistic, so we can never fully rule out the existence of a small factor. Nevertheless, for small exponents under 100,000, all of these have been ECM tested to a sufficient level that their undiscovered factors must surely be much, much longer than 65 bits. Most likely at least 80 bits for all exponents under 100,000 and at least 115 bits for all exponents under 10,000. And if we restrict it to only those exponents that have no known factors at all, then their undiscovered factors are probably at least 115 bits for exponents under 100,000 and 165 bits for exponents under 10,000. The odds of finding any factors that would be a lot smaller than this are astronomically low. Also, based on the work of an enigmatic user named TJAOI, we can be nearly certain that every exponent up to 1 billion has been factored to at least 64 bits. See this post and the entire thread about this user. Sometime next year, TJAOI will have completed the 65 bit level as well. However, TJAOI uses a different method which doesn't involve explicitly trial factoring each exponent, and we have only empirical evidence (albeit pretty strong empirical evidence) that the 64-bit level has been fully covered in a systematic way. In the specific case of M1277, this is the smallest Mersenne number with no known factors. So a lot of effort has been thrown at it, including ECM testing both within GIMPS and outside of it. The same is true of other very small exponents. An example would be M1471, where a factor was recently found externally and was "imported" into Primenet. Last fiddled with by GP2 on 2017-11-18 at 17:52
 2017-11-25, 09:39 #5 DanielBamberger   "Daniel Bamberger" Nov 2017 Marburg, Germany 33 Posts I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 257 and 258 beyond doubt? I am thinking about something like 14503921, where GIMPS first gave no factor below 267, until a factor was found in the previously unchecked 265-266 range.
2017-11-25, 10:00   #6
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts

Quote:
 Originally Posted by DanielBamberger I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 257 and 258 beyond doubt?
Any single member of this forum would gladly bet their life savings that there is no such factor.

Even aside from all this ECM stuff, the odds alone that GIMPS actually did do the original TF work are extremely good -- just a record keeping problem along the way.

 2018-01-20, 16:02 #7 vasyannyasha     "Vasiliy" Apr 2017 Ukraine 1111002 Posts Actually we have determenistic P-1 Pollard test. On mersenne.ca we see B1=5*10^12 So the minimum P-1 factorisation is B1*B1 Which is 2.5*10^25. Log2(2.5*10^25)=84.4 So "No factors below 2^84"
2018-01-20, 16:21   #8
xilman
Bamboozled!

May 2003
Down not across

23×32×139 Posts

Quote:
 Originally Posted by vasyannyasha Actually we have determenistic P-1 Pollard test. On mersenne.ca we see B1=5*10^12 So the minimum P-1 factorisation is B1*B1 Which is 2.5*10^25. Log2(2.5*10^25)=84.4 So "No factors below 2^84"
Almost, but not quite true. Suppose that P-1 is p*B1 smooth, where p is a small prime under B1, but not B1 smooth.

2018-01-21, 04:05   #9
axn

Jun 2003

2×2,297 Posts

Quote:
 Originally Posted by vasyannyasha Actually we have determenistic P-1 Pollard test. On mersenne.ca we see B1=5*10^12 So the minimum P-1 factorisation is B1*B1 Which is 2.5*10^25. Log2(2.5*10^25)=84.4 So "No factors below 2^84"
This is not how P-1 works
Quote:
 Originally Posted by xilman Almost, but not quite true. Suppose that P-1 is p*B1 smooth, where p is a small prime under B1, but not B1 smooth.
You mean small prime over B1? Small prime under B1 is, by definition, B1 smooth, yes?

2018-01-21, 05:24   #10
CRGreathouse

Aug 2006

22·5·293 Posts

Quote:
 Originally Posted by DanielBamberger I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 257 and 258 beyond doubt?
1. No, but it is possible to use ECM like that: Chelli has a collection of curves that are guaranteed to find all primes up to 2^32. (And of course see vasyannyasha and xilman above on P-1 and (non-)powersmooth numbers.)

2. The expected number of prime factors between 2^57 and 2^58 is log(log(2^58)) - log(log(2^57)) = 0.0173917.... Such primes have 18 decimal digits.

For a first estimate of how likely this is, there were 280+640+1580+4700+9700+17100+46500+112000+154504 = 347004 curves at or above 25 digits. Treating the higher levels as if they were no more likely to find a small factor (an underestimate), divide this total by 107, the number of curves to find a number at the 20-digit level, to get the expected number of times you'd find a prime of this size (if there was one to find), which is about 3243. Now the chance that you'd miss all of them is best if there is only one to find, in which case the odds are about exp(-3243) or 1 in 10^1400. That's like the chance that you and I pick 17 electrons out of the universe at random, only to discover we've chosen the same ones as each other.

But we can do better! Rather than treating all the curves as if they were at the 20-digit level, we can use Alex Kruppa's rho.gp to see that the chances are closer to 3 in 10^216145. See the code below, which has the B1, B2, nr = k*dF^2, and type and degree of polynomial (positive is power, negative is Dickson) to use for Brent-Suyama:

Code:
V=[[50000,12746592,280,1310720,2], [250000,128992510,640,12582912,-3], [1000000,1045563762,1580,100663296,-6], [3000000,5706890290,4700,536870912,-6], [11000000,35133391030,9700,3221225472,-12], [44000000,240491351116,17100,21474836480,-12], [110000000,776278396540,46500,68719476736,-30], [260000000,3178559884516,112000,274877906944,-30], [800000000,15892582605916,154504,1374389534720,-30]];
g(u)=my(p=ecmprob(u[1],u[2],precprime(2^58),u[4],u[5], 0)); -log(1-p)*u[3];
lambda=vecsum(apply(g,V))
exp(-lambda)
(The values come from gmp-ecm 6.4.4, others have slightly different values.) Now that mindbogglingly tiny number is the chance that a well-shuffled deck of 50,619 cards would happen to be exactly in order.

2018-01-21, 06:31   #11
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts

Quote:
 Originally Posted by CRGreathouse That's like the chance that you and I pick 17 electrons out of the universe at random, only to discover we've chosen the same ones as each other. ...Now that mindbogglingly tiny number is the chance that a well-shuffled deck of 50,619 cards would happen to be exactly in order.
Like I said previously, and sufficiently aware-of-this forum member would happily bet their life savings against having such a factor.

 Similar Threads Thread Thread Starter Forum Replies Last Post Jeff Gilchrist Wagstaff PRP Search 10 2013-04-07 11:07 TObject Data 7 2012-06-13 14:42 MatWur-S530113 PrimeNet 11 2009-01-21 19:08 dave_0273 Marin's Mersenne-aries 5 2004-12-24 12:54 Jeff Gilchrist NFSNET Discussion 2 2004-09-27 23:40

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

Sun Jun 7 01:14:03 UTC 2020 up 73 days, 22:47, 0 users, load averages: 1.76, 1.58, 1.48