20171118, 04:55  #1  
"Daniel Bamberger"
Nov 2017
Marburg, Germany
11011_{2} 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:


20171118, 07:22  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·23·223 Posts 
Quote:
2^{65} 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. 

20171118, 13:32  #3 
Einyen
Dec 2003
Denmark
2^{2}·3·5·7^{2} 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. 
20171118, 17:51  #4 
Sep 2003
2^{2}·3·5·43 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 64bit 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 20171118 at 17:52 
20171125, 09:39  #5 
"Daniel Bamberger"
Nov 2017
Marburg, Germany
33_{8} Posts 
I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 2^{57} and 2^{58} beyond doubt? I am thinking about something like 14503921, where GIMPS first gave no factor below 2^{67}, until a factor was found in the previously unchecked 2^{65}2^{66} range.

20171125, 10:00  #6  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:
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. 

20180120, 16:02  #7 
"Vasiliy"
Apr 2017
Ukraine
3C_{16} Posts 
Actually we have determenistic P1 Pollard test.
On mersenne.ca we see B1=5*10^12 So the minimum P1 factorisation is B1*B1 Which is 2.5*10^25. Log2(2.5*10^25)=84.4 So "No factors below 2^84" 
20180120, 16:21  #8 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·23·223 Posts 
Almost, but not quite true. Suppose that P1 is p*B1 smooth, where p is a small prime under B1, but not B1 smooth.

20180121, 04:05  #9  
Jun 2003
2×3^{4}×29 Posts 
Quote:
You mean small prime over B1? Small prime under B1 is, by definition, B1 smooth, yes? 

20180121, 05:24  #10  
Aug 2006
3×5^{2}×79 Posts 
Quote:
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 20digit 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 20digit 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 BrentSuyama: 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(1p)*u[3]; lambda=vecsum(apply(g,V)) exp(lambda) 

20180121, 06:31  #11  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Big factors  Jeff Gilchrist  Wagstaff PRP Search  10  20130407 11:07 
ECM factors  TObject  Data  7  20120613 14:42 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
100 P1 factors...  dave_0273  Marin's Mersennearies  5  20041224 12:54 
The factors of 11,199  Jeff Gilchrist  NFSNET Discussion  2  20040927 23:40 