mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2017-11-18, 04:55   #1
DanielBamberger
 
"Daniel Bamberger"
Nov 2017
Marburg, Germany

2710 Posts
Default 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?
DanielBamberger is offline   Reply With Quote
Old 2017-11-18, 07:22   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

281216 Posts
Default

Quote:
Originally Posted by DanielBamberger View Post
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.
xilman is offline   Reply With Quote
Old 2017-11-18, 13:32   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22×3×5×72 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2017-11-18, 17:51   #4
GP2
 
GP2's Avatar
 
Sep 2003

258010 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2017-11-25, 09:39   #5
DanielBamberger
 
"Daniel Bamberger"
Nov 2017
Marburg, Germany

33 Posts
Default

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.
DanielBamberger is offline   Reply With Quote
Old 2017-11-25, 10:00   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

1C3516 Posts
Default

Quote:
Originally Posted by DanielBamberger View Post
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.
Dubslow is offline   Reply With Quote
Old 2018-01-20, 16:02   #7
vasyannyasha
 
vasyannyasha's Avatar
 
"Vasiliy"
Apr 2017
Ukraine

22×3×5 Posts
Default

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"
vasyannyasha is offline   Reply With Quote
Old 2018-01-20, 16:21   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

281216 Posts
Default

Quote:
Originally Posted by vasyannyasha View Post
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.
xilman is offline   Reply With Quote
Old 2018-01-21, 04:05   #9
axn
 
axn's Avatar
 
Jun 2003

469810 Posts
Default

Quote:
Originally Posted by vasyannyasha View Post
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 View Post
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?
axn is online now   Reply With Quote
Old 2018-01-21, 05:24   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

592510 Posts
Default

Quote:
Originally Posted by DanielBamberger View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-01-21, 06:31   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

722110 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Big factors Jeff Gilchrist Wagstaff PRP Search 10 2013-04-07 11:07
ECM factors TObject Data 7 2012-06-13 14:42
Missing factors at the 'Known Factors' page MatWur-S530113 PrimeNet 11 2009-01-21 19:08
100 P-1 factors... dave_0273 Marin's Mersenne-aries 5 2004-12-24 12:54
The factors of 11,199- Jeff Gilchrist NFSNET Discussion 2 2004-09-27 23:40

All times are UTC. The time now is 07:10.

Mon Sep 28 07:10:39 UTC 2020 up 18 days, 4:21, 0 users, load averages: 1.29, 1.49, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.