mersenneforum.org Smallest exponent for mersenne not-factored
 Register FAQ Search Today's Posts Mark Forums Read

 2018-11-03, 16:04 #1 preda     "Mihai Preda" Apr 2015 2·677 Posts Smallest exponent for mersenne not-factored 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.
 2018-11-03, 16:08 #2 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 43·107 Posts I think you want this https://www.mersenne.org/report_ecm/ Second chart
2018-11-03, 20:28   #3
preda

"Mihai Preda"
Apr 2015

135410 Posts

Quote:
 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?

2018-11-03, 20:50   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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?

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

2018-11-03, 20:52   #5
GP2

Sep 2003

13×199 Posts

Quote:
 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.

Last fiddled with by GP2 on 2018-11-03 at 21:49

2018-11-03, 21:03   #6
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

47×107 Posts

Quote:
 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.

Last fiddled with by kriesel on 2018-11-03 at 21:06

 2018-11-03, 21:35 #7 GP2     Sep 2003 1010000110112 Posts Off-topic 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.
2018-11-03, 23:10   #8
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

3×1,579 Posts

Quote:
 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.

Last fiddled with by VBCurtis on 2018-11-03 at 23:11

2018-11-03, 23:17   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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.

 2018-11-03, 23:21 #10 ATH Einyen     Dec 2003 Denmark 1100000001002 Posts 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. Last fiddled with by ATH on 2018-11-03 at 23:24
2018-11-04, 00:47   #11
lycorn

Sep 2002
Oeiras, Portugal

1,451 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Data 558 2021-04-07 16:33 c10ck3r Data 49 2017-12-10 19:39 UberNumberGeek Factoring 51 2017-02-13 20:30 mattmill30 Factoring 3 2016-08-14 18:09 Mini-Geek PrimeNet 2 2006-08-26 10:15

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

Sun Apr 18 15:01:29 UTC 2021 up 10 days, 9:42, 0 users, load averages: 1.75, 1.56, 1.45