Choices for Manual Assignments
 

Hello,

The choices for manual assignments on this page [URL]http://www.mersenne.org/manual_assignment/[/URL] are a little different from what we see in the Prime95 "Worker Windows" menu. So I have a couple of questions --

1) What criteria would one use to select "World record tests" vs. "Smallest available first-time tests" (or vice versa)?

2) How or where does "ECM factoring" fit in the GIMPS scheme of things?

Sorry for asking yet more noob questions!

Rodrigo

[quote=Rodrigo;230285]1) What criteria would one use to select "World record tests" vs. "Smallest available first-time tests" (or vice versa)?[/quote]
The only difference between "World record tests" and "Smallest available first-time tests" is that WRT is constrained to hand out an exponent greater than that of the largest known Mersenne prime. That is, it's guaranteed to be a world record if if it turns up prime; a regular first-pass exponent, by contrast, could be below the world record, still working on filling in lower exponents that have not yet been tested.

Currently, the lowest exponent without an LL test is in the vicinity of 36M; however the largest known Mersenne prime is M43112609. See [URL]http://www.mersenne.org/primenet/[/URL] for a detailed breakdown; any of the numbers in the "LLERR" and "NO-LL" columns between 36M and 43M are fair game for "Smallest available first-time tests" but not "World record tests".

Note that many of the exponents in those "holes" below 43112609 are currently assigned, so the lowest available [i]unassigned[/i] number at any given moment may be greater than the world record, in which case the two options will be identical. The main difference is that WRT is [i]guaranteed[/i] to give you something bigger than the world record.
[quote]2) How or where does "ECM factoring" fit in the GIMPS scheme of things?[/quote]
ECM (Elliptic Curve Method) is a factorization method which is somewhat more resource-intensive than trial factoring, but can find much bigger factors. Each individual ECM curve is run on a random starting value (called the [i]sigma[/i]); it's a probabilistic method, so as you complete more curves at a given bound, the probability of your having found a factor of a given size increases. Thus, the Primenet server hands out individual curves to clients for a given number until a certain factor size level has been cleared; then it moves on to a higher bound for the next factor size level.

ECM is actually very similar to P-1 (IIRC, it's a generalization of that method). However, due to its relative resource-intensiveness, it is not a practical method of removing factors from potential prime candidates. Rather, it's used on much lower, known-composite numbers to further efforts to get their [i]complete[/i] factorizations.

Note that even though ECM and P-1 are related, P-1 is NOT a probabilistic method. If there is a factor that will be found by P-1 at a given bound, then one run of P-1 will find it. ECM, however, is never guaranteed to find a factor after a given number of curves.

mdettweiler,

Thanks very much for the excellent, detailed explanation!

You lead me to a follow-up question:

How are the "World record tests" and "Smallest available first-time tests" on the manual assignments page, different from the "First time tests" in the Worker Windows?

I guess that, at bottom, what I'm wondering about is the reason for the difference in the nomenclature -- why don't the manual assignments page and the Prime95 menu simply offer the same choices with the same names? They offer [B]some[/B] of the same work options, but then also [B]different[/B] ones. Is there a reason for the differing but overlapping sets of options?

Rodrigo

[quote=Rodrigo;230324]mdettweiler,

Thanks very much for the excellent, detailed explanation!

You lead me to a follow-up question:

How are the "World record tests" and "Smallest available first-time tests" on the manual assignments page, different from the "First time tests" in the Worker Windows?

I guess that, at bottom, what I'm wondering about is the reason for the difference in the nomenclature -- why don't the manual assignments page and the Prime95 menu simply offer the same choices with the same names? They offer [B]some[/B] of the same work options, but then also [B]different[/B] ones. Is there a reason for the differing but overlapping sets of options?

Rodrigo[/quote]
They both offer the same work options, just worded differently. :smile: For instance, "Smallest available first-time tests" on the website = "First time tests" in Worker Windows. Similarly, "World record tests" = "World record sized numbers to test"; "TF-LMH" = "Trial factoring to low limits"; etc.

[quote=mdettweiler;230334]They both offer the same work options, just worded differently. :smile: For instance, "Smallest available first-time tests" on the website = "First time tests" in Worker Windows. Similarly, "World record tests" = "World record sized numbers to test"; "TF-LMH" = "Trial factoring to low limits"; etc.[/quote]
Thanks, mdettweiler, this is a great help!

Knowing the situation as you do -- Could I put in for a change to standardize the nomenclature from one to the other (website to software)? For example, except for your patient explanation I wouldn't have known that "first-time tests" are the same as "smallest available first-time tests," or that "trial factoring to low limits" is the same as "TF-LMH." Surely there are other folks out there scratching their heads, but too embarrassed to ask?

Rodrigo

[quote=Rodrigo;230285]1) What criteria would one use to select "World record tests" vs. "Smallest available first-time tests" (or vice versa)?
[/quote]
[quote=mdettweiler;230294]The only difference between "World record tests" and "Smallest available first-time tests" is that WRT is constrained to hand out an exponent greater than that of the largest known Mersenne prime. That is, it's guaranteed to be a world record if if it turns up prime; a regular first-pass exponent, by contrast, could be below the world record, still working on filling in lower exponents that have not yet been tested.

Currently, the lowest exponent without an LL test is in the vicinity of 36M; however the largest known Mersenne prime is M43112609. See [URL]http://www.mersenne.org/primenet/[/URL] for a detailed breakdown; any of the numbers in the "LLERR" and "NO-LL" columns between 36M and 43M are fair game for "Smallest available first-time tests" but not "World record tests".

Note that many of the exponents in those "holes" below 43112609 are currently assigned, so the lowest available [I]unassigned[/I] number at any given moment may be greater than the world record, in which case the two options will be identical. The main difference is that WRT is [I]guaranteed[/I] to give you something bigger than the world record.
[/quote]One minor exception:

While a "World record tests" exponent is greater than that of the largest known Mersenne prime [I]at the time the assignment is made[/I], this does [U]not[/U] mean that it's "guaranteed to be a world record if if it turns up prime" or "[I]guaranteed[/I] to give you something bigger than the world record"!

Why?

A new world record may have been set with a larger exponent than yours, by someone else, while you were testing your exponent. This circumstance is unlikely, but it [U]is[/U] possible.

[quote=cheesehead;230372]A new world record may have been set with a larger exponent than yours, by someone else, while you were testing your exponent. This circumstance is unlikely, but it [U]is[/U] possible.[/quote]
cheesehead,

That makes sense, thanks.

Rodrigo

[quote=Rodrigo;230336]For example, except for your patient explanation I wouldn't have known that "first-time tests" are the same as "smallest available first-time tests," or that "trial factoring to low limits" is the same as "TF-LMH." Surely there are other folks out there scratching their heads, but too embarrassed to ask?

Rodrigo[/quote]Just a note: GIMPS software messages were not all created in concert, at the same time. As the project has evolved, terminology that was clear in one place has sometimes been rendered ambiguous by additional ranges or functions added elsewhere years later.

GIMPS is a volunteer effort. If you really, really want to see some change made, get the source code, figure out what to change, test it on your own system, then send George Woltman a before/after/changes/documentation/test-case-results listing for the affected parts. :-) Or at least do the part about figuring out all the source code, file content and documentation changes.

cheesehead,

Well, I'm not a programmer, so that rules out the source code part. :smile:

Procedurally speaking, how would one go about suggesting changes to the labels for the various work types so that they match? And, which set of labels (the manual assignments web page or the Prime95 Worker Windows menu) would you say is the "more" accurate or up to date?

Of course, now that I know what the labels mean, from my perspective there's less of a need to standardize them. But I gotta think that this has puzzled other folks, too, and maybe even deterred some of them from participating or continuing to participate in GIMPS, as they wonder what's what.

Now, from a purely selfish standpoint, that would suit me just fine as it means less competition for the awards :evil: , but I don't think that way. At least not ALL of the time... :grin:

As a pretty recent newcomer I'm keenly aware of the steep learning curve involved, and anything that would tend to reduce it is bound to help the overall project in terms of the number of participants. I suspect that it might be helpful to newcomers to have more uniform naming of the various work types across the board, although I'm not sure that I'd be the most qualified person either to put the idea into a detailed proposal (see three paragraphs above) or to actually carry it out (see four paragraphs above).

But I'd be happy to put together a list of pages across the various web sites and pages where the labels might be able to use some standardization. Of course, the first question would be which set of labels to use as a starting point (the Manual Assignments page or the Worker Windows menu), and that decision might hinge on practical issues (such as, which one is easier to change) as much as on issues of "up-to-dateness."

One last thing: If folks who are already in the know consider that this would be too much effort for the potential benefit, or if they prefer not to tinker with things as they are, I can go along with that too. I'm not trying to make waves here...

Just my $0.02. Thanks for explaining about the evolution of the project, that too makes a lot of sense.

Rodrigo

[QUOTE=cheesehead;230377]GIMPS is a volunteer effort. If you really, really want to see some change made, get the source code, figure out what to change, test it on your own system, then send George Woltman a before/after/changes/documentation/test-case-results listing for the affected parts. :-) Or at least do the part about figuring out all the source code, file content and documentation changes.[/QUOTE]

Well yeah, but it's not unreasonable to request that the ones in charge make the change, especially when it's a simple text change like this, and not something like a major feature or rewrite. Especially since you can't edit the source of PrimeNet.
When you start talking about making real changes to the workings of the program, sure it's good to have an idea of the source code and even suggest what needs to be changed.

You're both right.

I think I was having low blood sugar when I wrote that one. That tends to narrow ones thinking. Sorry, I didn't recognize that at the time.

[quote=cheesehead;230539]I think I was having low blood sugar when I wrote that one. That tends to narrow ones thinking. Sorry, I didn't recognize that at the time.[/quote]
cheesehead,

No problem. And I understand: I keep my own tank topped up when I'm working.

Rodrigo

This thread has good questions and good answers.

I just want to add that I too would appreciate a little fine-tuning and standardization of the nomenclature.

[I]Possibly completely new options could be added, but that's part of my wish to make this project as optimized and coordinated a factoring project as it is a prime finding project. So that should be the topic for another thread.[/I]

lorgix,

The funny thing is that, soon after this thread, the disparate labels somehow started making sense to me. Maybe it's because writing for the thread made me think about them harder than before. Or maybe I simply got reeled into the Matrix...

I'd be curious to hear your ideas about adding "completely new options." Start a new thread with a title like that, and let's see what happens.

Rodrigo

I'm assuming the goal is to keep the interface and terminology as simple as possible without losing functionality. So calling what is essentially the same thing different names in different places isn't in our interest.


Regarding factoring;

I'm talking about factoring that is beyond that which is currently assigned through GIMPS.
[URL]http://www.mersenneforum.org/showthread.php?t=13302[/URL]
The above link leads to a thread regarding factoring numbers with exponents smaller than 5000000; clearly not directly connected to the [B]G[/B]reat [B]I[/B]nternet [B]M[/B]ersenne [I][B]P[/B]rime[/I] [B]S[/B]earch.

Some other people have asked pretty much the same questions as me, but I can't seem to find the threads...

I've been planning to try and straighten this out a bit before starting a thread about it, if a new one is necessary that is. There may already be one out there.

Certainly there are a lot of "sub-projects" going on... and a lot of esoteric terminology and jargon can make it harder to find the right place.

[U]I'm gonna try to crystallize the essence of the concept here;[/U]

GIMPS and PrimeNet are optimized for finding new and, in most cases, bigger primes. Or at least that's the goal.

This is done by coordinated, distributed work. Making reservations, keeping track of progress etc. And calculating the optimal amount of TF and P-1 to do, in order to save LL tests.

I would like Prime95 and PrimeNet to also have a "factoring option" or something to that effect. Having the goals of
1. Fully factoring Mersennes.
2. Finding factors to known composite Mersennes.
3. Finding factors to any Mersenne.

[B]PrimeNet&GIMPS:Prime finding::[what I'm thinking of]:Factor finding[/B]

A lot of work that falls into this category is being done, and some is also more or less coordinated through this forum. I'd like to see it implemented in the system.

The extent to which different algorithms are applied would then be determined with the goal of finding factors.

There is ofc overlap between this and how the system operates today. But once a number is declared composite (by testing or factoring) the following efforts to factor it can often times be described as a scrambled mess.

I can think of several ways to go about this... One could assign the task that is most likely to yield a new factor, given the hardware and time at hand. One could aim to maximize efficiency by working on what should give the highest [factor size squared]/[effort], (roughly... you get the point, hopefully). One could also allow users to choose to concentrate their efforts to a range or a single number, optimizing parameters given conditions like hardware etc. We might also be able to combine P-1 and ECM efforts better. And avoid the same P-1 being done several times.

[B]How this relates to your question about new options:[/B]
Various options aiming for the smallest not yet completely factored number, the smallest number without known factors, work mode (P-1, ECM, TF..), work unit size.... and/or combinations of a number of those.

I'm sure you get the idea.

[B]Anyone reading this:[/B]
1. Please make some noise if you think this idea is good.
2. Please explain any flaw you see.
3. Please point out any thread already dealing with this or related matters.

Wow... big post.. think I'm starting to ramble. Anyway, just putting it out there. If there is some interest; there will be a new thread. Hopefully less rambling.

Let's Put This in Its Own Thread
 

To the Forum Gods:

This is very interesting and, for maximum exposure, IMHO deserves to be in its own thread!

Rodrigo

lorgix,

I'm asking the Forum administrator to put this in its own thread, as it really deserves to stand out and be seen.

I'm relatively new here, and not a mathematician, so I'm far from the most qualified person to comment on your proposals. But they certainly deserve a hearing, and I'm not aware of the issues being discussed extensively before. But if they have been, then at the very least this might serve to reprise the topic.

My first thought would be that the goal of GIMPS really is to find new Mersenne primes, and so once a number has been shown not to be prime there is no purpose in trying to factor it completely; but I could be wrong and I sure would like to hear what more knowledgeable members have to say about this.

And yes, there are a number of independent or semi-independent projects covered in this forum, which can contribute to the "chaotic" impression. I myself am contributing one of my PCs to Operation Billion Digits, which is one of the ones I understand better. That said, I'm not sure if these other projects could or should be more formally incorporated into GIMPS and/or the Prime95 software (the latter would imply more work for the project's founder :wink:), but again this is an interesting topic and I'd be curious to see what other people have to say.

Thanks for bringing up these issues.

Rodrigo

I too think the idea deserves a thread, I'm just not certain it doesn't already exist.

You are correct, trying to completely factor a number isn't directly related to finding new primes. I should add that I don't hold any math degree either.

But factoring numbers can help further our understanding of numbers.

I guess we should also consider the fact that this computing is already being done.

That leaves us with two conditions to be met:

1. Sufficient interest from project participants.
2. Interest from the people behind the project.

Those things said, factoring is essential to the [B]G[/B]reat [B]I[/B]nternet [B]M[/B]ersenne [B]P[/B]rime [B]S[/B]earch as it is. Could we possibly make that factoring more efficient, while at the same time making the above mentioned (sub-projects and such) more efficient and coordinated?

Frankly, I don't think the two concepts are competing (and why would they?). People who really want to split M1061 will be working on that, and people who dream about finding the first 10^[some integer larger than 7]-digit prime will be looking for that.
The question is (in other words this time); is there enough interest to incorporate these ideas/develop the project in this direction to some extent?

A lot of stuff going on in this forum is beyond my knowledge. But if I get =>1 informed and though through response(s) to this, then =>1 person(s) will learn something from this. :smile:

[QUOTE=Rodrigo;235458]My first thought would be that the goal of GIMPS really is to find new Mersenne primes, and so once a number has been shown not to be prime there is no purpose in trying to factor it completely;[/QUOTE]

There is no purpose in trying to find new Mersenne primes. They're not useful for anything. We do it because it interests and entertains us. Some of us are also interested and entertained by finding factors of known-composite Mersennes, even if that doesn't contribute to the effort to find primes.

The official goal of GIMPS is indeed to find new Mersenne primes. But I think we can infer other goals from what GIMPS actually does. Specifically it is a [I]de facto[/I] goal to learn as much as we can about the factors of prime-exponent Mersenne numbers. Every such number can be placed in one of four ranks, based upon what we know about its factors:

1. We know nothing about its factorisation.
2. We know that it is composite, but we don't know any factors.
3. We know at least one factor.
4. We know its complete factorisation.

Note that known Mersenne primes are rank 4. If we know a number is prime, we know its complete factorisation.

Viewed through the lens of this secondary goal, there are some deficiencies in the exponent status report in the case where at least one factor is known. First, it no longer reports factoring limits, which it would be useful to know if we are to do further factorisation work on the number. Secondly it does not keep track of whether the cofactor has been tested for primality, and if so, what was the result. Consequently, we may know a Mersenne number's complete factorisation (because its cofactor is actually prime), but not know that we know it (because the cofactor has not been tested, or the results of a test have not been recorded).

[QUOTE=Mr. P-1;238172]
Viewed through the lens of this secondary goal, there are some deficiencies in the exponent status report in the case where at least one factor is known. First, it no longer reports factoring limits, which it would be useful to know if we are to do further factorisation work on the number. Secondly it does not keep track of whether the cofactor has been tested for primality, and if so, what was the result. Consequently, we may know a Mersenne number's complete factorisation (because its cofactor is actually prime), but not know that we know it (because the cofactor has not been tested, or the results of a test have not been recorded).[/QUOTE]

Yes! I've been thinking about this for a while. We don't know what work has been done on numbers with known factors, except ECM.

[QUOTE=lorgix;238225]Yes! I've been thinking about this for a while. We don't know what work has been done on numbers with known factors, except ECM.[/QUOTE]


Yes. The ECM status page by default shows exponents up to 2500. Since all of them have been ECMed to the 40 digit level, there's really no point in doing further TF, regardless of how much TF has actually been done. It's also a safe bet that the cofactors are known composite, and that they've been adequately P-1ed. However as you go further up the chart, these assumptions become more and more dubious.

[QUOTE=Mr. P-1;238230]Yes. The ECM status page by default shows exponents up to 2500. Since all of them have been ECMed to the 40 digit level, there's really no point in doing further TF, regardless of how much TF has actually been done. It's also a safe bet that the cofactors are known composite, and that they've been adequately P-1ed. However as you go further up the chart, these assumptions become more and more dubious.[/QUOTE]

Doing P-1 on larger numbers with known factors could be of interest. But again, with all previous efforts being obscured as soon as a factor is found...

I'm guessing database size is a problem.

[QUOTE=lorgix;238235]I'm guessing database size is a problem.[/QUOTE]

I don't know whether database size is a problem. I imagine it's just that recording and coordination beyond the minimum necessary to find primes has been developed in a rather [I]ad hoc[/I] fashion.

I have a concrete example of what I've been talking about: M106391. This number has a 58 bit factor almost certainly discovered long ago by TF. The cofactor, according to [URL=http://www.garlic.com/~wedgingt/factoredM.txt]Eddington's list[/URL] "is at least a pseudo-prime in some base other than 2" according to his [URL=http://www.garlic.com/~wedgingt/mersfmt.txt]explanation of the codes[/URL]. Yet someone has done 15 curves on it.

Instead of ECM, further work on this exponent should focus on strengthening its probable prime status, (alternatively, proving that it is in fact composite, whereupon ECM could resume), in preparation for a future primality proof. At over 32,000 digits, a proof is probably unfeasible currently, but it may be reachable with a few years.

[QUOTE=lorgix;235452] But once a number is declared composite (by testing or factoring) the following efforts to factor it can often times be described as a scrambled mess.

I can think of several ways to go about this... One could assign the task that is most likely to yield a new factor, given the hardware and time at hand. ... One could also allow users to choose to concentrate their efforts to a range or a single number, optimizing parameters given conditions like hardware etc. We might also be able to combine P-1 and ECM efforts better. And avoid the same P-1 being done several times.[/QUOTE]

IMHO I think GIMPS does a pretty good job on pre and post factoring - that is, when you allow the server to manage assignments.
1. TF to the recommended number of bits -1
2. P-1 with calculated parameters
3. Last bit of TF
4. ECM systematically.

Now, because this is an open volunteer participation project is actually quite easy for any of us to "choose" work assignments differently. Right or wrong, I am among the list of people who have done so more for personal reasons than purely what is best for GIMPS.

Some examples:
- M1061 to 62 bits has been TF'd well beyond recommended parms because someone thought/hoped/wished that maybe the factor is just one bit higher. But being the lowest composite not yet factored there is a lot of strong interest is being the one to factor it.
- When you see an exponent P1'd many times (1000003) it is simply a case of someone not fully understanding how P1 works; that subsequent P1s with slightly higher parms have a VERY SMALL chance of succeeding.

But notice that, other than possibly pointing this out to them, NO ONE is going to stop you from working on whatever you so choose.

[QUOTE=petrw1;238268]IMHO I think GIMPS does a pretty good job on pre and post factoring - that is, when you allow the server to manage assignments.
1. TF to the recommended number of bits -1
2. P-1 with calculated parameters
3. Last bit of TF
4. ECM systematically.

Now, because this is an open volunteer participation project is actually quite easy for any of us to "choose" work assignments differently. Right or wrong, I am among the list of people who have done so more for personal reasons than purely what is best for GIMPS.

Some examples:
- M1061 to 62 bits has been TF'd well beyond recommended parms because someone thought/hoped/wished that maybe the factor is just one bit higher. But being the lowest composite not yet factored there is a lot of strong interest is being the one to factor it.
- When you see an exponent P1'd many times (1000003) it is simply a case of someone not fully understanding how P1 works; that subsequent P1s with slightly higher parms have a VERY SMALL chance of succeeding.

But notice that, other than possibly pointing this out to them, NO ONE is going to stop you from working on whatever you so choose.[/QUOTE]

GIMPS does a good job, no doubt.

But for factoring other than ECM; a little more record keeping would be nice.

I can understand that it might not have the highest priority though.

[QUOTE=Mr. P-1;238257]I have a concrete example of what I've been talking about: M106391. This number has a 58 bit factor almost certainly discovered long ago by TF. The cofactor, according to [URL=http://www.garlic.com/~wedgingt/factoredM.txt]Eddington's list[/URL] "is at least a pseudo-prime in some base other than 2"[/QUOTE]

For what it's worth, I've just calculated (using PFGW) that this number is a 3-PRP and a 7-PRP.

[QUOTE=Mini-Geek;238270]For what it's worth, I've just calculated (using PFGW) that this number is a 3-PRP and a 7-PRP.[/QUOTE]

Also 13-PRP, 17-PRP and 31-PRP.

[QUOTE=petrw1;238268]IMHO I think GIMPS does a pretty good job on pre and post factoring - that is, when you allow the server to manage assignments.
1. TF to the recommended number of bits -1
2. P-1 with calculated parameters
3. Last bit of TF
4. ECM systematically.[/QUOTE]

This is only the case with exponents where no factor is known. Once a factor is found, support for continued efforts to decompose the cofactor is much weaker.

[QUOTE]Some examples:
- M1061 to 62 bits has been TF'd well beyond recommended parms because someone thought/hoped/wished that maybe the factor is just one bit higher. But being the lowest composite not yet factored there is a lot of strong interest is being the one to factor it.[/QUOTE]

M1061 has also had multiple P-1s and far more ECM than is warranted, including several thousand curves with B1=1000000 during the past few months. That's too low a bound to find factors much above 35 digits, but other ECM has established that it is highly unlikely to have a factor below 60 digits. M1061 is probably beyond ECM.

[QUOTE=lorgix;238275]Also 13-PRP, 17-PRP and 31-PRP.[/QUOTE]

Attached are all the factored prime-exponent Mersenne numbers from Eddington's list, for which the cofactors are known to be PRP, but not proven prime. Anyone fancy working through it to establish that they are PRP to several bases? Proving the smaller ones prime?

With a bit more work, it should be possible to massage his data files to obtain a list of factored prime-exponent Mersennes whose cofactors are status unknown. It might be worth PRP testing some of these.

Have I just started a new subproject?

I think a PRP test (or many, in different bases) should be fairy easy on those numbers.

Why don't you post them on a new factoring thread with the pfgw command line switches?

Luigi

[QUOTE=Mr. P-1;238281]Attached are ... prime-exponent Mersenne numbers ...[/QUOTE]

Either 7135 is prime or I screwed up somehow.

[QUOTE=Mr. P-1;238283]Either 7135 is prime or I screwed up somehow.[/QUOTE]

There is indeed a lot of composites in the list. The smallest prime exponents have been completely factored.

I fixed the list.

With a bit more parsing of data files, here is a list of all exponents which are listed in the mersenne.org ECM progress tables, but which Eddington has down as fully factored. The smallest, M12451 has had a considerable amount of ECM work, some of which no doubt yielded the 80 bit factor, but some of which may have been a waste of effort since that factor was found.

The 1146digit factor of M4219 has been proved by factordb.

I'm running the 1431digit cofactor of M4871 through Primo.

It's PRP to all bases=<97.

I will probably post the certificate in about six hours.

[QUOTE=lorgix;238357]The 1146digit factor of M4219 has been proved by factordb.

I'm running the 1431digit cofactor of M4871 through Primo.

It's PRP to all bases=<97.

I will probably post the certificate in about six hours.[/QUOTE]

The 1431digit factor of M4871 is definitely prime.

You missed 32351 btw (composite exponent).

The 12395digit cofactor of M41263 is PRP using all prime bases =<37.

I trust you'll submit these to Eddington.

The 63-bit factor of M14561 was probably discovered by P-1 (B1=2551, B2=461639 would do it). If this is the case, then every one of the at least 280 curves at B1=50,000 and 251 curves at B1=250,000 were a waste of time.

[QUOTE=lorgix;238373]You missed 32351 btw (composite exponent).[/QUOTE]

I was only considering prime exponents. I had assumed that the ECM Progress on the PrimeNet server, only tracked these. Is that not the case?

Appart from mprime, the only tool I have installed on my system is pari/gp, which isn't that good for this sort of thing. Do you think you will do all those feasible? Or should I install something else and help?

[QUOTE=Mr. P-1;238375]I trust you'll submit these to Eddington.

The 63-bit factor of M14561 was probably discovered by P-1 (B1=2551, B2=461639 would do it). If this is the case, then every one of the at least 280 curves at B1=50,000 and 251 curves at B1=250,000 were a waste of time.[/QUOTE]

I'm assuming this Eddington person would only be interested in the proof certificate.

Yeah, I'm pretty sure that must have been found by P-1. Damn, all the time wasted...

[QUOTE=Mr. P-1;238376]I was only considering prime exponents. I had assumed that the ECM Progress on the PrimeNet server, only tracked these. Is that not the case?[/QUOTE]

Nvm, I screwed up, typo.

[QUOTE=Mr. P-1;238378]Appart from mprime, the only tool I have installed on my system is pari/gp, which isn't that good for this sort of thing. Do you think you will do all those feasible? Or should I install something else and help?[/QUOTE]

Unfortunately, my computer is old and slow. If you're thinking about absolute proofs then I'd rather leave that to someone with more computing power. But PRPs are fast, I'm running the whole list now.

[CODE](2^6199-1)/179635392927728929353086482614805697378612611809363271
(2^6337-1)/4501318288109788011334762909785912975982707465271020857512756782053472363053668157533504357730278762590457
(2^7417-1)/7507005070637706149786475668997639973991
(2^9901-1)/126963693135213650972501160277833204460511647031933548221705424113461245441590718863886455178721617007207585872256907920259294592750741967
(2^10007-1)/20453755399107134938775648992529401
(2^10169-1)/10402314702094700470118039921523041260063
(2^10211-1)/306772303457009724362047724636324707614338377
(2^11813-1)/14740786026020930383
(2^12451-1)/87065160674565854360715728029229940740377
(2^14561-1)/8074991336582835391
(2^14621-1)/19171116593282984132708214394856581399
(2^17029-1)/418879343
(2^17683-1)/14570261281140293911854048050469358706809858630769
(2^20887-1)/118421949251433453827857391594130772157699369945439163022281
(2^26903-1)/1113285395642134415541632833178044793
(2^28759-1)/226160777
(2^28771-1)/104726441
(2^29473-1)/139640239316440423720389373549494109943
(2^32531-1)/1641222175081417
(2^41263-1)/1379707143199991617049286121
(2^41521-1)/41602235382028197528613357724450752065089
(2^57131-1)/61481396117165983261035042726614288722959856631
(2^58199-1)/237604901713907577052391
(2^63703-1)/42808417
(2^82939-1)/883323903012540278033571819073
(2^86371-1)/41681512921035887
(2^87691-1)/806957040167570408395443233
(2^106391-1)/286105171290931103
(2^130439-1)/260879
(2^136883-1)/536581361
(2^173867-1)/52536637502689
(2^221509-1)/292391881
(2^271211-1)/613961495159
(2^271549-1)/238749682487
(2^406583-1)/813167[/CODE]I've finished all but the last two. All 3-PRP so far. -edit: All 3-PRP

[QUOTE=lorgix;238385]I'm assuming this Eddington person would only be interested in the proof certificate.[/QUOTE]

A cert would allow him to promote a 'd' to a 'D'. (Alternatively a witness would convert it to a C.) It's possible, given how quickly your "old and slow" computer was able to generate a cert for cofactor:M4871, that he may already have one, and that his list is just out of date.

However it can't hurt to send it him, and your PRP confirmations, which strengthen confidence in the 'd' designation.

[QUOTE]Yeah, I'm pretty sure that must have been found by P-1. Damn, all the time wasted...[/QUOTE]

A counterargument is that the wasted curves are only a tiny fraction of a percent of the total ECM work done on all exponents, so don't really matter too much.

[QUOTE]Unfortunately, my computer is old and slow. If you're thinking about absolute proofs...[/QUOTE]

Eventually, yes, but PRPs will do for now. Do you intend to do any more that 3-PRP on them?

I suppose I should parse his lists to find the first few 'status unknown' cofactors, to see if any are small enough to be PRP-tested.

[QUOTE=lorgix;238225]Yes! I've been thinking about this for a while. We don't know what work has been done on numbers with known factors, except ECM.[/QUOTE]

Huh? The only other work that there is to do is factor it completely
with SNFS. We certainly do know what work has been done.

[QUOTE=R.D. Silverman;238469]Huh? The only other work that there is to do is factor it completely
with SNFS. We certainly do know what work has been done.[/QUOTE]

We are talking about all partially-factored prime-exponent Mersennes, not just the small ones. M8000053, for example, has a 27 bit factor, undoubtedly discovered long ago by TF. It's way too large for SNFS now or in the foreseeable future, but additional TF, P-1, or ECM might yeild more factors. Unfortunately, the database doesn't tell us how much TF beyond 27 bits or P-1, if any, has been done on this number. Nor does it tell us whether any primality or PRP tests have been done on the cofactor

You, personally, might not be interested in the discovery of additional factors short of complete factorisation. But other people are.

[QUOTE=Mr. P-1;238415]Eventually, yes, but PRPs will do for now. Do you intend to do any more that 3-PRP on them?

I suppose I should parse his lists to find the first few 'status unknown' cofactors, to see if any are small enough to be PRP-tested.[/QUOTE]

I've tested them with bases =<7. 11 is done up to and including the cofactor of M86371 right now. And yes, all PRP so far.

I feel like this is too quick and easy to not have been done before... but maybe to few people care about extending factorizations.

[QUOTE=lorgix;238507]I feel like this is too quick and easy to not have been done before... but maybe to few people care about extending factorizations.[/QUOTE]

Eddington says they're all PRP to at least one base > 2. At this point, I think we can safely say they're all almost certainly prime.

[QUOTE=Mr. P-1;238515]Eddington says they're all PRP to at least one base > 2. At this point, I think we can safely say they're all almost certainly prime.[/QUOTE]

All 11-PRP too. OK.


There are two numbers with less than 2000digits.

M6199 has a 1813digit cofactor
M6337 has a 1802digit cofactor

I tested those two numbers with 10 other bases.

Anyone feel like proving those?

[QUOTE=lorgix;238357]The 1146digit factor of M4219 has been proved by factordb.[/QUOTE]

[url]http://www.mersenneforum.org/showpost.php?p=232133&postcount=6[/url]

[QUOTE=Mr. P-1;238591][URL]http://www.mersenneforum.org/showpost.php?p=232133&postcount=6[/URL][/QUOTE]

[URL]http://factorization.ath.cx/index.php?id=1100000000214492699[/URL]

I don't know which happened first.

[QUOTE=lorgix;238526]All 11-PRP too. OK.


There are two numbers with less than 2000digits.

M6199 has a 1813digit cofactor
M6337 has a 1802digit cofactor

I tested those two numbers with 10 other bases.

Anyone feel like proving those?[/QUOTE]

It seems an easy test with Primo...

E.T.

[QUOTE=ET_;238607]It seems an easy test with Primo...

E.T.[/QUOTE]

I was hoping someone would see it like that.

[CODE](2^6199-1)/179635392927728929353086482614805697378612611809363271
(2^6337-1)/4501318288109788011334762909785912975982707465271020857512756782053472363053668157533504357730278762590457[/CODE]Still no proof, afaik.

TO THE PRIMOBILE!!

[QUOTE=Mr. P-1;238257]I don't know whether database size is a problem. I imagine it's just that recording and coordination beyond the minimum necessary to find primes has been developed in a rather [I]ad hoc[/I] fashion.[/QUOTE]

The data I have is about 33 GB but some of that is simply historical rather than current. I've retained all output from my own runs, e.g., and all email sent to me related to Mersenne numbers.

[QUOTE=Mr. P-1;238257]I have a concrete example of what I've been talking about: M106391. This number has a 58 bit factor almost certainly discovered long ago by TF. The cofactor, according to [URL="http://www.garlic.com/%7Ewedgingt/factoredM.txt"]Eddington's list[/URL] "is at least a pseudo-prime in some base other than 2" according to his [URL="http://www.garlic.com/%7Ewedgingt/mersfmt.txt"]explanation of the codes[/URL]. Yet someone has done 15 curves on it.[/QUOTE]

I'm "Eddington" - Will Edgington, to correct the spelling (and I've only had half a dozen people get it right when they first hear it for some reason, so don't feel bad). I rarely have time to visit forums but thought I would take a look today after getting Oscar's email about M4871.

The 58 bit factor of M106391 is likely from GIMPS but I can find out for sure if someone wants to know; it should be in my files somewhere.

The ECM curves may have been done before the 58 bit factor was found.

That the cofactor is SPRP was almost certainly done by me with a program from the mers package that I maintain (see my web site, which I've added to my profile here). The current version of that program, sprpgmp, actually does 20 SPRP tests with random bases, so it is almost certainly SPRP to 20 distinct bases but may - if the random bases all happened to be identical - be SPRP for only one base. Perhaps I should modify the program to ensure the random bases are distinct.

[QUOTE=Mr. P-1;238257]Instead of ECM, further work on this exponent should focus on strengthening its probable prime status, (alternatively, proving that it is in fact composite, whereupon ECM could resume), in preparation for a future primality proof. At over 32,000 digits, a proof is probably unfeasible currently, but it may be reachable with a few years.[/QUOTE]

There are many much smaller SPRP cofactors to prove, including a few with less than 1200 digits for which the ECPP program I have has failed. Since I use Linux rather than MSWindows, most authors of such programs don't support my use of their programs.

Welcome to the forum, Will!

I'm just recently realizing how little interest there is in extending factorizations...

Would you be interested in sorting out the data so that we can start proving primes and identifying composites to factor? :smile:

[QUOTE=wedgingt;238686]I'm "Eddington" - Will Edgington, to correct the spelling (and I've only had half a dozen people get it right when they first hear it for some reason, so don't feel bad).[/QUOTE]

My apologies. In my defense I will say that I've lost my glasses and am using an older pair which is no longer fully up to the job.

[QUOTE=Mr. P-1;238257]Instead of ECM, further work on this exponent should focus on strengthening its probable prime status, (alternatively, proving that it is in fact composite, whereupon ECM could resume), in preparation for a future primality proof. At over 32,000 digits, a proof is probably unfeasible currently, but it may be reachable with a few years.[/QUOTE]

[QUOTE]There are many much smaller SPRP cofactors to prove, including a few with less than 1200 digits for which the ECPP program I have has failed.[/QUOTE]

I wasn't suggesting that work be done on it ahead of other tasks. My point was that further ECM should [i]not[/i] be done, and it should be removed from the PrimeNet's ECM progress list.

[QUOTE=Mr. P-1;238490]We are talking about all partially-factored prime-exponent Mersennes, not just the small ones. M8000053, for example, has a 27 bit factor, undoubtedly discovered long ago by TF. It's way too large for SNFS now or in the foreseeable future, but additional TF, P-1, or ECM might yeild more factors. Unfortunately, the database doesn't tell us how much TF beyond 27 bits or P-1, if any, has been done on this number. Nor does it tell us whether any primality or PRP tests have been done on the cofactor

You, personally, might not be interested in the discovery of additional factors short of complete factorisation. But other people are.[/QUOTE]

As an example of the additional data that I have, here is what I have for this exponent and some of its neighbors that have data. Note that not all of the exponents are prime. 'H' is highest trial factoring, 'c' is digits in the composite cofactor (by LL test when there's no known factor), 'o' is P-1 bounds, 'C' is a known factor, etc. The format is described on my web site and programs I've written can read and write it.

M( 8000023 )H: 18446744073709551616
M( 8000023 )c: 2408247
M( 8000023 )o: 40000 450000
M( 8000026 )C: 864002809
M( 8000027 )C: 13200044551
M( 8000028 )C: 32000113
M( 8000033 )C: 395137629937
M( 8000033 )C: 1906187238989927
M( 8000033 )H: 2252229690409151
M( 8000038 )C: 792003763
M( 8000039 )C: 16000079
M( 8000041 )C: 48000247
M( 8000044 )C: 96000529
M( 8000050 )C: 8000051
M( 8000051 )C: 208001327
M( 8000051 )H: 9223372036854775808
M( 8000053 )C: 128000849
M( 8000053 )H: 9223372036854775808
M( 8000054 )C: 7552050977
M( 8000055 )C: 400002751
M( 8000056 )C: 14576102033
M( 8000057 )C: 48000343
M( 8000063 )C: 4211141722479911
M( 8000063 )H: 4503696666331951

[QUOTE=lorgix;238705]Welcome to the forum, Will!

I'm just recently realizing how little interest there is in extending factorizations...

Would you be interested in sorting out the data so that we can start proving primes and identifying composites to factor? :smile:[/QUOTE]

A lot of the data I have - nearly everything I have for prime exponents, e.g. - is on my web site. The smallest SPRP cofactors should be these. The first number after each 'd' (for "done", SPRP; 'D' is proven prime) is the cofactor; the second is the digits minus a fraction to allow my programs and scripts to sort them easily.
[code]
M( 4219 )C: 1634011915849
M( 4219 )C: 374348373815829857290734641903689
M( 4219 )C: 258085857757974624851934511097909374553
M( 4219 )C: 114993958477860428006858637956899699352321
M( 4219 )d: 611760320622902352693563428449827662833646555447394683993819887538653675159640546733294091435820678232847626728051311780486811992314060627280478124081246395367703065395628379229798484567033524980508298147381834842500517830771374326809992638093139763810900687459164776113881615120459020462993776191592628995187839512977555362842959599478236653029838269308344211903085271243864467522611982029685391369080765381925813330175419136171535468101767517057398672944647191786723993659555007707603474001622909538891185590651175590146890078742678787022838445618439025055391215178467257472363573515546737491872715105970159809948170002967447184206415504848281735415747373152186315868967197261143118100201293384979173989195922701785531873124767561468941841946749950458321454508943794516298236207482100740060326753815159848709310401022966571062387772521308913974551313672437241755776788437379944108451611736441089464518954373003909879958388559207171086674076763610779308296545549597719818266789389462349764636508037921227902307683540324022910269080927604507456508722592493836895095053574286360007503273274450411618538059187487509397564902691853893964372609625959 1145.9997629770

M( 7736 )C: 15473
M( 7736 )d: 9204491083726541729266567601471444329696631442344981431080754304338517202479825704708168361584443220173159746955658319872226827894696158427067368155867113488065513258508747555444435213793714645707333231354709392097881839581182784326394055584833662570305406399842719309326889563391133205121809640737536847612190163876346404787817387525638094982013601782945250606972114988322647360650287694307006008987227557105771507174425909017893011796996993964961154355753480435864294553880686455000837365767828673806742459951938371437326566489572167787070595907923956337478965698716896738108637875683461439370672939945722664550460118112314840960437168628395852506252366614840117258891067154642808373550316537689707097385866475178034598724990199374366941091632039248444592165926072488503954436734636696960611114179555123828676842815894123511610807438661339141915801655793131755397177593505570978799199492340891265152845166543749678711505995868169443966984963587657337523315541043519335991932587032243221833506118827959949035567629728410565768244083641612636803390113309291344892066167245002709645081207176400738835471592939623580395456780283517466070695133155570570494491777 1158.9998707342

M( 19320 )C: 1922335012613589603121
M( 19320 )d: 196379032258501556024415676425163706687541839294586972240452328978156114335863862009741402502598509804856922845147601135536745817573693899103382513811439525465020329680448574265807984163199392380855605393462072974810440395092334566713531332962694741922304458757315121278339240593529332024287658018380324546749139608299516086467126326309316159664431996961756069737915384761883061888266947579612804420346700281106164262300333619532351916132555257490332361537692624809832787157249810950795337533953407118109708915927472925955002123723882850879065605319514889897398677582405705996122769084129400888794874491888927112761649141199226859843967254941151499388196078709046916748038593402484467762026476450750100937458887901968787453157519897353844026633985109234553403279362094792022872618073109325326136526370534932388362822155851932425799224314982415615679303595071661230226591709326244326655825657770982771235993754464087584834062234871378980470839377623390266223263161961137371290048108594561250674167098384156621014196009516880649650468447512777219325494960634853345004956080341996261874111188971156812759463969249148060501837163348351761780347832177622997420095846470785287526053719548241280664958041154007473367374475649625858763805170414860250013119201 1250.9999482402

M( 12918 )C: 160003471867
M( 12918 )C: 1644335785369
M( 12918 )C: 5044861106732953267
M( 12918 )d: 431589574935531353309018531528828891172605069305527622299502156711176952536155695763413037400701037585916093015928470422492225238544843196176670311446191068558470000690155545433573374896329062638377598073286126572303130670635240867764895156295561298607815401715713632911520351740730049209904743282048118090995179615567564382016808434438846904591105527881685266212035710082593515191024592237932382297233850725215617614882601436224366289964975102525617187521619148069533903230444880134798290780459895458685451586756056091521239575036885707367648144325041266579211791903604286273812388046693691316985970394441720968695593608950053227381883288663156111270887947198025965768577510037111307401242634276977913185529303745857850138965693311338518615148164561119869369402105097487874775677540992157756904525645883251492069836366428336200876062079097376513420921474876304551852077009733949067444120570384575879351268057539594505481295786480457280800923515367020187951039303452584251327247154917711326188675102109143233185013159331994587257348461394806622365105991194104462098505313353637995735696313450324061791299828943408716037286301931775831297808064874629871874710227586616530843015227636173746935723298765282402036785646696465118867690188357911353669608593251 1253.9999225886
[/code]
I should have ECPP primality certificates for all shorter proven prime cofactors.

The smallest known-composite cofactors and smallest SPRP cofactors can also be pulled from my data fairly easily.

For data that is very wide or high, (like yours with the long cofactors) it's preferred that you put it in [code] tags for better formatting. :smile:

[COLOR="Purple"]Added in moderation[/COLOR]

[QUOTE=wedgingt;238964]As an example of the additional data that I have, here is what I have for this exponent and some of its neighbors that have data. Note that not all of the exponents are prime. 'H' is highest trial factoring, 'c' is digits in the composite cofactor (by LL test when there's no known factor), 'o' is P-1 bounds, 'C' is a known factor, etc. The format is described on my web site and programs I've written can read and write it.[/QUOTE]

Thanks for that. From what I've been able to work out, based upon what it says on your website (which may be out of date), your downloadable files include the factors of all fully-factored Mersenne numbers (FactoredM.txt), data (including factors and factoring limits) on all other Mersenne Numbers less than 200,000 (LowM.txt), and all factors of all incompletely-factored prime-exponent Mersenne Numbers (results.pfk).

Additionally you keep, but don't make available on your website, data, including factoring limits, on all Mersenne numbers with exponents up to 2^31, and for larger prime exponents. Clearly you also keep data on some composite-exponents above this boundary too, based upon the sample you gave above.

I'm grateful that you keep this data, but it's format and availability doesn't lend itself to a large-scale factoring effort in the way that PrimeNet does. I also wonder how complete and up-to-date it is? For example, the ECM work recorded in LowM for M929 seems a lot less than PrimeNet is showing.

[QUOTE=Mr. P-1;238977]For example, the ECM work recorded in LowM for M929 seems a lot less than PrimeNet is showing.[/QUOTE]

For many years Will has been the world's keeper of Mersenne factors. Keeping track of the world's ECM, TF, and P-1 work is, however, a nearly impossible task. Will can only reasonably know about what people tell him. Most projects and most people do not tell anyone about factoring failures.

[QUOTE=wblipp;239074]For many years Will has been the world's keeper of Mersenne factors. Keeping track of the world's ECM, TF, and P-1 work is, however, a nearly impossible task. Will can only reasonably know about what people tell him. Most projects and most people do not tell anyone about factoring failures.[/QUOTE]

I intend no criticism of Will. Quite the contrary: I'm grateful he maintains the info he does. My point is that it would be better if PrimeNet could be extended to coordinate this work. At least, that's what it looks like to someone on the outside who isn't aware of the constraints PrimeNet may operate under.

I ran the cofactor of M5087. It has probably been done before...

Would anyone care to compile a list of cofactors that are yet to be proven?

Prime or SPRP cofactors of Mersenne numbers
 

[QUOTE=lorgix;241925]I ran the cofactor of M5087. It has probably been done before...

Would anyone care to compile a list of cofactors that are yet to be proven?[/QUOTE]

In case anyone is still interested, I have started to get back into this stuff after moving in January and just uploaded current data to a new 'mers' project on sourceforge.

In particular, see:

[URL]https://sourceforge.net/projects/mers/files/data/factoredM.txt/download[/URL]

... for the current state of Mersenne numbers that are completely factored - the cofactor is either proven prime ('D') with primo by me or SPRP according to the sprpgmp program in the mers package that I still maintain, now at that new sourceforge project, 'mers'.

-- Will

Will, your data is somewhat outdated. There is a definitive list at [url]http://www.mersenne.ca/prp.php[/url], although non-prime exponents are not considered at all.

All the probable-prime cofactors of Mersenne numbers with prime exponents less than or equal to M63,703 have been certified prime, mostly with primality certificates from Primo.

These primality certificates can be downloaded from factordb.com, for example go to
[URL="http://factordb.com/index.php?query=M63703"]the M63703 page[/URL] and click on [URL="http://factordb.com/index.php?id=1100000000013096896"]the cofactor[/URL] and then click on "Primality" to expand it, and "Download" to download the certificate file.

Above that (M82,939 and higher), no one has ventured to attempt to prove primality. The difficulty rises rather rapidly for higher exponents.

Newly discovered PRP cofactors are usually announced in [URL="http://mersenneforum.org/showthread.php?t=19407&page=39"]the oddly-titled "disbelievers" thread[/URL] on this forum.

Thanks, I had noticed factordb.com while trying to catch up here on the forums and have been pulling data from GIMPS automatically for years and been running on my own PCs when I have such that don't overheat ...


... including getting mfaktc working on my Linux box, pulling trial factoring tasks from and sending its results to the GIMPS web site automatically.


I'll start working on scripts to pull data from factordb.com and mersenne.ca; since I'm already using primo myself, adding that data should be straight forward.


Thanks, Will

mers package: small update, mostly noting move to Sourceforge
 

Sourceforge says there have been 45 downloads already and this is the only place I have mentioned that, so ...


I noticed that there were still mentions of my old ISP, garlic.com, so I've changed those to mention Sourceforge or my newer personal email at
gmail.com.


I'm currently working on adding testing of the Perl scripts - I know they work fine for me (I've been using them for years now) but they aren't very well documented yet and I'm not sure how portable they are. I use them on Ubuntu Linux and MSWindows10 with Cygwin.



My primary email address is still [email]wedgingt@acm.org[/email].


Feel free to report any issues via Sourceforge's ticket system or email to me.



Thanks, Will

factordb vs my data
 

It looks like I have several primo primality certificates that factordb doesn't.
I've already uploaded a few by hand but it's hard to tell which ones I have that it doesn't, so I will likely end up automating the process, which will be messy.

In the other direction, I'll probably automate searching factordb for certificates my scripts are about to try to create.



-- Will

Primality certificates
 

I have now uploaded all of my primality certificates to factordb.com; there were a couple dozen I had that it didn't.


I'm now starting to find the certificates it has that I don't and verify them, starting with the cofactor of M63703 mentioned here.


Thanks, Will

I'm now slowly downloading data from factordb.com and comparing it with what I already have. Often, it has factors I didn't and, somewhat less often, I have factors that it didn't.
The same script uploads any factors it didn't have and downloads any primality certificates it has so I can retain and verify them.
For half a dozen or so (prime and composite) exponents under 16,000 or so, it had a factor I did not and vice versa and having all the factors resulted in a complete factorization, so I did those proofs with primo and uploaded them.
-- Will