me, myself and I

[prgamma10]

Originally Posted by ramgeis

If false reports are possible, wouldn't that mean that the announcement of M( p ) as the n-th Mersenne prime must include at least one factor for each non-prime M( p' ) with p' < p ?

Factorizing is very, very difficult.

[davieddy]

Originally Posted by Batalov

ProducingFaking the second manual result "on the GPU" after having the complete residue known from the CPU can be easily done even by a 9-year old. Changing the order and submitting the "GPU" result first - by a clever 9-year old ...or by any 10-year old.

It has been demonstrated that two matching results (with different shifts, and produced with unfettered Prime95 binary) are easily produced for any input. Maybe not by a 10-year old though...

I was a clever 9-year-old 54 years ago.
Are you suggesting that finding a square root in modular arithmetic is about as simple as division? (extended Euclid or the like).

David

[Mini-Geek]

Originally Posted by ramgeis

In other words, the whole LL-checking process only reduces the chance to prove that M( p ) is prime and can't prove that M( p ) isn't prime, right?

If false reports are possible, wouldn't that mean that the announcement of M( p ) as the n-th Mersenne prime must include at least one factor for each non-prime M( p' ) with p' < p ?

As long as we accept results from untrusted parties, you're right, we can't be absolutely sure that we haven't missed a prime. Mentions of which Mersenne prime you're dealing with already must (to be accurate) carry disclaimers that some numbers smaller than the prime have yet to be checked and double checked (e.g. Wikipedia on M43-M48). There is still the exceedingly small chance that a Mersenne prime was missed due to everyone's standards not being good enough, but it's generally not mentioned.

If you want to improve the standards, you can begin by triple checking the most suspicious residues (e.g. ones submitted by the same user on the same date), then moving on to less suspicious ones. I recall a mini-project being formed to do just this and dying out due to lack of interest.

If you want factors, then you really don't know things starting as low as M1277. Is M1279 really the 15th Mersenne prime? If I said that I LL tested M1277, would you believe me, or do you only trust yourself? For that matter, why trust the software that runs LL tests, or tells you that 3454817 is a factor of M1009? Should you trust hand calculations more? I certainly wouldn't. So what does it really mean to know something? To what standards do you want composite Mersenne numbers checked? GIMPS has its own standards, albeit somewhat easily gamed. The standards for primes are much higher: different software, different hardware, different trusted people. I think most would agree this is overkill for composites.

[Batalov]

Originally Posted by ramgeis

In other words, the whole LL-checking process only reduces the chance to prove that M( p ) is prime and can't prove that M( p ) isn't prime, right?

No. Correctly done LL test paired with a correctly done double-check is conclusive. But the server is insufficiently protected from fake results and fake double-checks.

Originally Posted by davieddy

I was a clever 9-year-old 54 years ago.
Are you suggesting that finding a square root in modular arithmetic is about as simple as division? (extended Euclid or the like).

No square roots were involved and only Prime95 27.9 was used for submissions: all legal and clear from the GIMPS server point of view. The exact procedure was sent to George. (Not described here to avoid copycats.) Some patches to the code might help this situation.

Originally Posted by Mini-Geek

As long as we accept results from untrusted parties, you're right, we can't be absolutely sure that we haven't missed a prime.

This is exactly right.

[Uncwilly]

Originally Posted by Mini-Geek

If you want to improve the standards, you can begin by triple checking the most suspicious residues (e.g. ones submitted by the same user on the same date), then moving on to less suspicious ones. I recall a mini-project being formed to do just this and dying out due to lack of interest.

The lower ranges have been well tested.
GIMPS competition (on the wayback machine) Dan Holle

http://mersenneforum.org/showthread.php?t=7479

http://mersenneforum.org/showthread.php?t=17108

[bloodIce]

Originally Posted by Mini-Geek

As long as we accept results from untrusted parties, you're right, we can't be absolutely sure that we haven't missed a prime.

So true, we just need to reduce the possible candidates by finding factors of the composite exponents. And re-test the holes . We will never be sure as the rest of the post suggests.

Originally Posted by Mini-Geek

If you want factors, then you really don't know things starting as low as M1277. Is M1279 really the 15th Mersenne prime? If I said that I LL tested M1277, would you believe me, or do you only trust yourself? For that matter, why trust the software that runs LL tests, or tells you that 3454817 is a factor of M1009? Should you trust hand calculations more? I certainly wouldn't. So what does it really mean to know something? To what standards do you want composite Mersenne numbers checked? GIMPS has its own standards, albeit somewhat easily gamed. The standards for primes are much higher: different software, different hardware, different trusted people. I think most would agree this is overkill for composites.

Who can argue with the presence of a factor(s)? With LL test is not the test per se, which is wrong, but the possibility to submit a wrong/manipulated result. If there are factors for all M<1279 and M1279 is prime by all standards you mentioned, than it is hard to say that is not the 15th. Here is one number only (M1277), but for the Mersenne primes to follow, the gaps are vast. Thereafter, I believe more factors are needed. One can check the divisibility of a composite by the factor with many different algorithms in a fraction of a second (no need of paper and pen I believe). So once we have factors, the tests on those numbers are easier (even with a pen, for the most pedantic ones ). The factors are the golden standard to prove a composite, right?

[Mini-Geek]

Originally Posted by bloodIce

So true, we just need to reduce the possible candidates by finding factors of the composite exponents. And re-test the holes . We will never be sure as the rest of the post suggests.

Who can argue with the presence of a factor(s)? With LL test is not the test per se, which is wrong, but the possibility to submit a wrong/manipulated result. If there are factors for all M<1279 and M1279 is prime by all standards you mentioned, than it is hard to say that is not the 15th. Here is one number only (M1277), but for the Mersenne primes to follow, the gaps are vast. Thereafter, I believe more factors are needed. One can check the divisibility of a composite by the factor with many different algorithms in a fraction of a second (no need of paper and pen I believe). So once we have factors, the tests on those numbers are easier (even with a pen, for the most pedantic ones ). The factors are the golden standard to prove a composite, right?

Finding factors is a great way to be sure a number is composite, but here's the problem: it's often EXTREMELY hard to find a factor. As an example, we can look at the lower bounds of what each (factoring vs LL) has yet to prove: The smallest Mersenne number with no factors known is M 1 277 (and I'll point out that a great deal of effort goes into fully factoring small Mersenne numbers - I'm sure that a lot of ECM has been run on this number). The smallest Mersenne number without matching LLs (to GIMPS's standards) is M 26 114 633.

I think the best bang-for-your-buck for raising the certainty of composite Mersenne numbers is, perhaps after a small amount of extra TF and/or P-1, simply to run another LL. (the factoring might be useful because GPUs are so good at TF and and poor P-1s might've been run the first time around)