Ultimate EFF Prize Limit of GIMPS

[jinydu]

I'm curious to know some opinions about this. What is the largest of the EFF prizes (http://www.eff.org/awards/coop.php) that GIMPS will ever receive? An estimate of the discovery dates would also be appreciated. Any other relevant comments are welcome.

[victor]

It depends on too many factors :D

I hope it will be $250,000!

[biwema]

Gimps found the last 8 largest primes, so it seems as if it will go on like that.

Fact is, that the number of mersenne primes is limited. It is easily possible that there is no mersenne prime with >10M decimal places less than M45000000.

Now other primalty testing algorithms get more and more efficient.
To find Sierpinskt and Proth primes with LLR (also based on George Woltmans code) is merely 10-15% slower than a LucasLehmer.
After reaching M38000000, it is possible that many people switch to Rieselsieve or Seventeen or Bust to test the smallest 10Mdigit numbers.

Also the Generalized Fermat numbers are getting more and more interesting:
staring around
3441463500^1048576 +1 or
11843670820000000000^524288 +1
gives many candidates with exactly 10 Million digits.

There is some competition around.

Any Predictions?

[JuanTutors]

sorry if you said 1M, because considering the trend, and the massive support of this program, any less than 10M just makes no sense.

I said 100M, because I can seriously see myself testing 100M Mersennes for however many years it takes.

Plus, there's no reason to believe that some nice improvements on the AKS test can't make it waayyyy faster. Plus, what if another randomized or absolutely polynomial time test appears that blows any of these tests off the map?

[R.D. Silverman]

Originally Posted by dominicanpapi82

Plus, there's no reason to believe that some nice improvements on the AKS test can't make it waayyyy faster. Plus, what if another randomized or absolutely polynomial time test appears that blows any of these tests off the map?

What is it that compels people who know NOTHING about a subject to make
ridiculous speculations?

(1) No possible improvement of AKS can ever make it faster than LL.
This is clear.
(2) LL *IS* a polynomial time test. To prove N prime, it requires
lg N multiplications mod N. Any test will require arithmetic mod N. The
only issue is how to reduce the number of operations mod N or to speed
the arithmetic. The multiplications used by LL run in nearly linear time.
We will not do better. [note that it takes linear time just to write down the
answer]
(3) A Theorem of Pomerance shows, essentially that we can never hope to
do better than O(lg N) multiplications in any test. All we might do is reduce
the implied constant. His theorem places a bound on the size of a primality
proof certificate.

Although a rigorous proof is lacking, there are strong reasons to believe
that LL is the fastest test that is theoretically possible. Now can we
please stop this blathering about "blows these tests of the map"?

[alpertron]

Mersenne hunting is not done by performing Lucas-Lehmer tests for all numbers of the form 2^p-1 (p prime).

Instead, the project tries to find small factors using trial division and p-1 in order to avoid the costly primality test. In this way about 60% of LL tests are not done.

What is needed is a way to quickly eliminate candidates without necessarily finding factors. For example if instead of 40% we would have to perform only the 5% of Lucas-Lehmer tests, the 10M prime should be found in relatively short time.

Is there a theorem that prevents such a method?

[ewmayer]

Originally Posted by alpertron

What is needed is a way to quickly eliminate candidates without necessarily finding factors. For example if instead of 40% we would have to perform only the 5% of Lucas-Lehmer tests, the 10M prime should be found in relatively short time.

Is there a theorem that prevents such a method?

No theorem, but it is generally believed that factoring is a "hard" problem, so it is exponentially more difficult to find factors <= N digits as N increases. The hard part in what you propose is not finding factors of more Mersenne numbers - that we can do if we simply expend more factoring effort - the hard part is doing so sufficiently cheaply to make it worth our while. To eliminate as large a fraction of M(p) as you mention would require oders-of-magnitude speedups in any or all of: sieving, p-1, and ecm, or a new class of factoring algorithm that is asymptotically faster (though it's still going to be exponential) than these for finding small factors of large input numbers. Such breakthroughs don't grow on trees.

[alpertron]

I didn't say factoring. What I want is a probabilistic primality test faster than Miller-Rabin, useful even if it fails say 5% of the time (MR virtually does not fail in the 10M-digit range). This would reduce about 10 times the number of candidates.

[JuanTutors]

Well is it possible that some other test is found for a number of a different form that, for a given size, is faster than the LL test?

Also, if someone says something ignorant, why not just save yourself the aneurysm sometimes? It's ok!! Some people aren't as smart as you!!

[R.D. Silverman]

Originally Posted by dominicanpapi82

Well is it possible that some other test is found for a number of a different form that, for a given size, is faster than the LL test?

Also, if someone says something ignorant, why not just save yourself the aneurysm sometimes? It's ok!! Some people aren't as smart as you!!

The issue is not intelligence, or lack thereof. It has NOTHING to do with
being smart.

The issue is doing one's homework. I assume that anyone sufficiently
interested in a subject will do background reading before indulging in idle
and ignorant speculation. And if one has NOT studied a subject, then,
to quote Tom Lehrer, "The least he can do is to shut up"

And, if you had bothered to read and understand my post, you would
realize that I already asnswered the question you now ask. Although a
formal proof is lacking, there is good reason to believe that no algorithm can
be faster than LL for *any* number.

Seeing the same ridiculous speculations over and over again about
"faster primality tests" from people who are clearly clueless about the subject
is TIRESOME.

[cheesehead]

Originally Posted by R.D. Silverman

What is it that compels people who know NOTHING about a subject to make ridiculous speculations?

"Curiosity"

"Human nature"

"Chance to push Silverman's 'hot button' again"

The issue is doing one's homework.

No, that's not the issue. (For details, inquiring readers may do a search on "homework" in the Math subforum to find my earlier exposition.)

I assume that anyone sufficiently interested in a subject will do background reading before indulging in idle and ignorant speculation.

So, either

some folks are insufficiently interested ... or

"will do background reading" is not precisely-enough defined ... or

your assumption is invalid.

(For purposes of this discussion, I'll withhold comment on discernment of "indulging in idle and ignorant speculation".)

And if one has NOT studied a subject, then, to quote Tom Lehrer, "The least he can do is to shut up"

You're fond of rules for situations in which one person is the authority figure, aren't you ... even in more open situations where you don't really have authoritarian control over others.

I once heard an interview in which Warren Buffett was quoted as replying, after having been asked what constituted wisdom, something like (this is my paraphrase) "Wisdom consists of having as many different models as possible, so that one may choose the most appropriate model to apply to any given situation."