M1277 - no factors below 2^65?

[DanielBamberger]

I am trying to confirm the information given in https://en.wikipedia.org/wiki/Mersen...rsenne_numbers. It states:

As of October 2017, the Mersenne number M1277 is the smallest composite Mersenne number with no known factors; it has no prime factors below 2⁶⁵.

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 2⁶⁵. From the "History" section, it seems that exponents between 2⁵⁷ and 2⁵⁸ have never been checked. Is this correct?

[xilman]

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 2⁶⁵. From the "History" section, it seems that exponents between 2⁵⁷ and 2⁵⁸ have never been checked. Is this correct?

GIMPS is not the only project attempting to factor this number.

2⁶⁵ 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.

[ATH]

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.

[GP2]

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.

[DanielBamberger]

I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 2⁵⁷ and 2⁵⁸ beyond doubt? I am thinking about something like 14503921, where GIMPS first gave no factor below 2⁶⁷, until a factor was found in the previously unchecked 2⁶⁵-2⁶⁶ range.

[Dubslow]

Originally Posted by DanielBamberger

I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 2⁵⁷ and 2⁵⁸ 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.

[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"

[xilman]

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.

[axn]

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

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?

[CRGreathouse]

Originally Posted by DanielBamberger

I know this is infinitesimally unlikely, but do the ECM tests exclude factors between 2⁵⁷ and 2⁵⁸ 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:

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.

[Dubslow]

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.