Smallest exponent for mersenne not-factored

[preda]

Hi, how can I query, or find, the smallest exponents "p" for which M(p) has no known factors?

I.e. it is known that M(p) is composite (e.g. through an LL or PRP test), but no factor was found through TF or P-1.

[petrw1]

https://www.mersenne.org/report_ecm/

Second chart

[preda]

Originally Posted by petrw1

https://www.mersenne.org/report_ecm/

Second chart

Thank you!

I'm surprised by how small those exponents are, without known factors. The smallest is 1277!

I looked at the P-1 already done. For 1277:
https://www.mersenne.org/report_expo...o=1277&exp_hi=
B1= 5 000 000 000 003
B2= 400 000 000 000 241

So somebody did a P-1 first-stage to 5*10^12, which is impressive! I wonder, is that residue (after the P-1 first-stage to high B1), the full 1277 bits of it, available somewhere?

[science_man_88]

Originally Posted by preda

Thank you!

I'm surprised by how small those exponents are, without known factors. The smallest is 1277!

I looked at the P-1 already done. For 1277:
https://www.mersenne.org/report_expo...o=1277&exp_hi=
B1= 5 000 000 000 003
B2= 400 000 000 000 241

So somebody did a P-1 first-stage to 5*10^12, which is impressive! I wonder, is that residue (after the P-1 first-stage to high B1), the full 1277 bits of it, available somewhere?

https://www.mersenneforum.org/showthread.php?t=19407

also TF of M1277 to 72 bits has as many k values as TF of 74000051 to 87 bits

[GP2]

Originally Posted by preda

I'm surprised by how small those exponents are, without known factors. The smallest is 1277!

...

So somebody did a P-1 first-stage to 5*10^12, which is impressive! I wonder, is that residue (after the P-1 first-stage to high B1), the full 1277 bits of it, available somewhere?

It is very unlikely to yield to further P−1.

The previous low record holder was M1061. It was finally factored by NFS into P143*P177, that is, its smallest factor is 474 bits and P−1 would have required B1=5.87906e+15 and B2=1.13383e+98 (!!)

Everyone looks at M1277 and imagines for a moment that they will be the hero. But that's not realistic.


Edit:

There is surprisingly little overlap between factors found by TF and factors found by P−1. Most factors found by TF have k that is far too unsmooth to be findable by P−1, and most factors found by P−1 have bit size that is far too large to be findable by TF.

However, I suspect that there is much more overlap between the factors findable by P−1 and the factors findable with a very sustained and deep ECM effort. In all likelihood, there has been more ECM, to deeper limits, than what has been recorded on our ECM progress page, and that probably already rules out the usefulness of further P−1 testing.

[kriesel]

Originally Posted by GP2

It is very unlikely to yield to further P−1.

The previous low record holder was M1061. It was finally factored by NFS into P143*P177, that is, its smallest factor is 474 bits and P−1 would have required B1=5.87906e+15 and B2=1.13383e+98 (!!)

Everyone looks at M1277 and imagines for a moment that they will be the hero. But that's not realistic.

For fun, I looked at the next entry in the table, 1619. To take that to B1=10^13, B2=10^15 was estimated as about 8 weeks on one of my prime95 workers (with 32GB ram allocated). The same worker can belt out three 89M candidates to prime95 default bounds daily, so the cost of such a try on m1619 would be about 170 current wavefront exponents not done, and probably about 5 not factored that would have been.

[GP2]

Here's something that we rarely think about: if our sole goal is to find new Mersenne primes, then factoring is actually not that significant at all.

When you do trial-factoring, the difficulty doubles every time you increment the number of bits. Exponentially increasing difficulty, so it's a very rapid transition from ridiculously easy to impossibly hard, with only a narrow transition zone.

With P−1 it's a similar story: you can find a lot of factors with ridiculously small B1 and B2, but then there are rapidly diminishing returns.

So you have tons of low-hanging fruit (which was picked many years ago) and tons of high-hanging fruit (which we will never ever reach), and only a relatively small amount of middle-hanging fruit.

About 55 to 60% of exponents have low-hanging fruit, about 30 to 35% have only high-hanging fruit. That leaves only 10% or so in the middle-hanging segment.

All of the tremendous TF factoring effort that is being done, not just now but into the indefinite future... will only ever find factors for a single-digit percentage of exponents, even under the most ideal circumstances.

Imagine for a moment if there had never been any factoring effort beyond the low-hanging fruit: just very basic TF to low bit depth and very basic P−1 with small limits. How much of a setback would that be for GIMPS, how much further behind would we be? The answer is, maybe only 5% behind, compared to where we actually are in present-day reality. In all likelihood we would already have discovered all of the 50 known Mersenne primes except possibly the most recent one, which might have taken an extra year or so to discover.

Yes, factoring is worth it if it saves more effort than two LL tests (though it's not clear that the current overkill deep TF work still meets those criteria), and factors are very cool in their own right, I search for them myself. A factored exponent is more secure knowledge than a primality-tested exponent, since verification can be done in a millionth of a second rather than weeks.

But overall, factoring has much less of an impact on the progress of the GIMPS project than we often realize.

[VBCurtis]

Originally Posted by GP2

In all likelihood, there has been more ECM, to deeper limits, than what has been recorded on our ECM progress page, and that probably already rules out the usefulness of further P−1 testing.

I agree with this; I've run something like 800 curves at large bounds (something like B1=3e9, B2 filled 32GB) on M1277. I ran these among 4 or 5 machines, and just never collected my log files to submit a detailed manual report. I imagine I am not the only one!

An SNFS factoring attempt on this number would require quite a lot of memory, so ECM to large bounds is our only hope in the next couple of years.

[science_man_88]

Originally Posted by GP2

But overall, factoring has much less of an impact on the progress of the GIMPS project than we often realize.

I guess ... 5% less exponents means the LL tests need 5% less, which allows them to go 5.26% faster per unit time. etc.

[ATH]

Further trial factoring from where we are now might have "little" impact, but in total it is a pretty big impact.


Up to 100M: 3,735,132 of 5,761,455 exponents (64,8%) has at least 1 known factor.
Up to 1000M: 29,489,324 of 50,847,534 exponents (58,0%) has at least 1 known factor.

I'm not sure what the ratio is of factors found by TF, ECM, P-1 is, and some of them was found after 1 or 2 LL test was already done, but it is still significant.

But yes there is still at lot of TF, ECM and P-1 going on below the double check limit which has zero impact on finding Mersenne Primes.

[lycorn]

Originally Posted by ATH

But yes there is still at lot of TF, ECM and P-1 going on below the double check limit which has zero impact on finding Mersenne Primes.

But also, as GP2 wrote a couple of posts above "factors are very cool in their own right".

They ARE there, so it is sort of an irresistible thing to try and dig them up.