mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-11-03, 16:04   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

7×173 Posts
Default 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.
preda is offline   Reply With Quote
Old 2018-11-03, 16:08   #2
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

41×107 Posts
Default I think you want this

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

Second chart
petrw1 is offline   Reply With Quote
Old 2018-11-03, 20:28   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

7×173 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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?
preda is offline   Reply With Quote
Old 2018-11-03, 20:50   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by preda View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-11-03, 20:52   #5
GP2
 
GP2's Avatar
 
Sep 2003

258010 Posts
Default

Quote:
Originally Posted by preda View Post
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
GP2 is offline   Reply With Quote
Old 2018-11-03, 21:03   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·52·89 Posts
Default

Quote:
Originally Posted by GP2 View Post
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
kriesel is online now   Reply With Quote
Old 2018-11-03, 21:35   #7
GP2
 
GP2's Avatar
 
Sep 2003

22·3·5·43 Posts
Default 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.
GP2 is offline   Reply With Quote
Old 2018-11-03, 23:10   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

103458 Posts
Default

Quote:
Originally Posted by GP2 View Post
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
VBCurtis is offline   Reply With Quote
Old 2018-11-03, 23:17   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-11-03, 23:21   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

55748 Posts
Default

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
ATH is offline   Reply With Quote
Old 2018-11-04, 00:47   #11
lycorn
 
lycorn's Avatar
 
Sep 2002
Oeiras, Portugal

23×52×7 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne number factored (disbelievers are biting elbows) alpertron Data 527 2020-09-28 11:28
Largest Mersenne Number Fully Factored? c10ck3r Data 49 2017-12-10 19:39
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors UberNumberGeek Factoring 51 2017-02-13 20:30
Exponent fully factored whilst only 74% known mattmill30 Factoring 3 2016-08-14 18:09
exponent factored? Mini-Geek PrimeNet 2 2006-08-26 10:15

All times are UTC. The time now is 19:34.

Mon Sep 28 19:34:56 UTC 2020 up 18 days, 16:45, 1 user, load averages: 1.88, 1.64, 1.69

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.